[백준] 가운데를 말해요 Java

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

풀이

 

이 문제같은 경우는 Time out에 집중

직관적인 로직으로 n만큼 입력받는대로 sort 하고 중간값 출력 >> 당연하게도 시간초과

 

시간초과 해결하기 위해서 for문으로 sort를 반복하는 방법 대신 priority queue를 사용해서 중간값을 도출

 

두 개의 priority queue 사용

하나는 최대힙

하나는 최소힙

왜?

그래야 내용물을 끄집어 내지 않고도 중간값 도출이 가능하니까

 

1. 두 우선순위 큐의 사이즈를 비교해서 같으면 최대힙에 삽입, 다르면 최소힙에 삽입

>> 입력값 개수가 짝수일 경우 작은 쪽을 중간값으로 출력해야 하기 때문에

 

2. 두 큐에서 우선순위가 가장 높은 원소의 값을 비교

 내림차순(최대힙) 쪽의 크기가 크면 두 값을 swap

 

3. 내림차순(최대힙) 에서 가장 높은 우선순위의 값을 결과 string에 저장

4. 결과값 출력

 

좀 더 자세하게 설명해보면

 

초기

[ ] [ ]

 

1 입력 

[1] [ ]

:: 두 큐의 사이즈가 동일하기 때문에 maxPq에 삽입

중간값 1

 

5 입력

[1] [5]

:: 두 큐의 사이즈가 다르기 때문에 minPq에 삽입

:: swap 안함

중간값 1

 

2 입력

[1 2] [5]

:: 두 큐의 사이즈가 동일하기 때문에 maxPq에 삽입

:: swap 안함

중간값 2

 

10 입력

[1 2] [5 10]

중간값 2

 

-99 입력

[-99 1 2] [5 10]

중간값 2

 

7 입력

[-99 1 2] [5 7 10]

중간값 2

 

5 입력

[-99 1 2 5] [5 7 10]

중간값 5

 

>> 결과값 1 1 2 2 2 2 5

 

 

** 문제에 나와있는 케이스에서는 swap의 필요성을 못느껴서 임의의 케이스를 써보면

 

10 입력

[10] [ ]

중간값 10

 

5 입력

[10] [5]

:: 여기서 maxPq.peek() > minPq.peek() 조건이 만족하기 때문에 두 값을 swap

[5] [10]

중간값 5

 

1입력

[1 5] [10]

중간값 5

 

3 입력

[1 5] [3 10]

:: 조건 만족하므로 swap

[1 3] [5 10]

중간값 3

 

>> 결과값 10 5 5 3

 

 

 

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();

        PriorityQueue<Integer> maxPq = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> minPq = new PriorityQueue<>();


        for(int i=0; i<n; i++){

            int k = Integer.parseInt(reader.readLine());

            if(maxPq.size() > minPq.size()){
                minPq.add(k);
            }
            else{
                maxPq.add(k);
            }

            if(maxPq.size()>0 && minPq.size()>0){
                if( maxPq.peek() > minPq.peek()){
                    int temp=maxPq.poll();
                    maxPq.add(minPq.poll());
                    minPq.add(temp);
                }
            }
            sb.append(maxPq.peek()+"\n");

        }
        System.out.println(sb);