백준 14729 칠무해

설명

처음에 간단하게 PriorityQueue를 통해서 풀려고 했는데 메모리초과가 발생했다.

문제의 메모리제한은 256MB인데, 원인을 찾아보니 PriorityQueue는 메모리를 많이 사용한다고 한다. 

그래서 방법을 찾던중 아래와 같이 접근해서 처리했다.

1. 8개까지 입력을 받는다.

2. 8개를 sort한다.

3. 다음 숫자가 들어오면 index 0번부터 비교를 한다. 

4. 자기보다 큰 숫자가 있으면 해당 위치에 넣기 위해 모두 오른쪽으로 1칸 옮긴다. 

5. 해당 index에 본인의 수를 기입한다. 

반례

# 첫번째 반례
10
100.000
100.000
100.000
100.000
100.000
100.000
50.000
0.000
50.000
0.000

# 두번째 반례
9
2
4
5
6
7
8
9
3
1

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // 14729
    public static void main(String[] args) throws IOException {
        process();
    }

    private static void process() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        double[] arr = new double[9]; // 8 보다 1 더 큰 9로 선언
        for (int i = 0; i < 8; i++) {
            arr[i] = Double.parseDouble(br.readLine());
        }
        Arrays.fill(arr, 8, arr.length, 9999);
        Arrays.sort(arr);

        for (int i = 0; i < N-8; i++) {
            double d = Double.parseDouble(br.readLine());

            // 앞에서부터 순회
            for (int j = 0; j < 7; j++) {
                if(arr[j] >= d) {
                    // 한칸씩 뒤로 미룸
                    for (int k = 7; k >= j; k--) {
                        arr[k+1] = arr[k];
                    }
                    arr[j] = d;
                    break;
                }

            }
        }

        // 포맷에 맞게 출력
        for(int i = 0; i < 7; i++) {
            bw.write(String.format("%.3f", arr[i]) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}