JAVA 백준 1655 가운데를 말해요 (우선순위 큐)

 

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

 

---

문제

1. 첫째 줄에 N ( 1 <= N <= 1000000 )을 입력.
2. 정수 ( -10000 <= 정수 <= 10000 ) N개를 입력하면서 수가 1개 입력될 때마다 어떠한 수를 출력해야 됨.
3. 현 시점까지 입력된 수 중에서 중간값을 출력.
4. 입력했던 수가 짝수개라면 중간에 잇는 두 수 중에서 작은 수를 출력.
5. 총 N번 출력.

---

 

 

초기 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        ArrayList<Integer> arr = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            arr.add(num);
            Collections.sort(arr);

            if (i == 0) {
                sb.append(num).append("\n");
            } else if (i == 1) {
                sb.append(arr.get(0)).append("\n");
            } else if (i % 2 == 1) {
                sb.append(arr.get(arr.size() / 2 - 1)).append("\n");
            } else {
                sb.append(arr.get(arr.size() / 2)).append("\n");
            }
        }

        System.out.println(sb);
    }
}

 

우선순위 큐를 사용하지 않고 arraylist를 사용해서 만들었더니 시간초과가 났다.

 

최종 코드(우선순위 큐를 사용하여 만든 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> leftQueue = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> rightQueue = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            if (leftQueue.size() == rightQueue.size()) {
                leftQueue.offer(num);
            } else {
                rightQueue.offer(num);
            }

            if (!leftQueue.isEmpty() && !rightQueue.isEmpty()) {
                if (leftQueue.peek() > rightQueue.peek()) {
                    int temp = leftQueue.poll();
                    leftQueue.offer(rightQueue.poll());
                    rightQueue.offer(temp);
                }

            }
            sb.append(leftQueue.peek()).append("\n");
        }

        System.out.println(sb);
    }
}

 

 

우선순위 큐 자료구조를 참고한 블로그

https://kbj96.tistory.com/49

 

이거 보고 우선순위 큐로 만들긴 했었는데 답이 계속 다르게 나와서

다른 블로그를 참조했다

 

왼쪽 큐의 숫자보다 작으면 왼쪽에 넣고 오른쪽 큐의 숫자보다 크면 오른쪽에 넣는 방식으로 하고 싶었는데 잘 안 됐다.

 

미련 남아서 만들어본 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> leftQueue = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> rightQueue = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            if (leftQueue.isEmpty()) {
                leftQueue.offer(num);
            } else if (rightQueue.isEmpty()) {
                rightQueue.offer(num);
            }

            if (i == 1 && !leftQueue.isEmpty() && !rightQueue.isEmpty()
                    && leftQueue.peek() > rightQueue.peek()) {
                int temp = leftQueue.poll();
                leftQueue.offer(rightQueue.poll());
                rightQueue.offer(temp);
            }

            if (i >= 2 && !leftQueue.isEmpty() && !rightQueue.isEmpty()) {
                if (leftQueue.peek() > num) {
                    leftQueue.offer(num);
                } else if (rightQueue.peek() < num) {
                    rightQueue.offer(num);
                } else if (leftQueue.peek() <= num && rightQueue.peek() >= num) {
                    if (leftQueue.size() <= rightQueue.size()) {
                        leftQueue.offer(num);
                    } else {
                        rightQueue.offer(num);
                    }
                }
            }

            sb.append(leftQueue.peek()).append("\n");
        }

        System.out.println(sb);
    }
}

 

예제만 잘 출력되고 다른 반례들은 잘 안 되고 틀린 것을 보아 잘못 만든 것 같다.

오른쪽이나 왼쪽 큐에 수가 치중되었을 경우 두 큐에 있는 수를 잘 분배하는 부분이 필요할 것 같다.

 

수정한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> leftQueue = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> rightQueue = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());

            if (leftQueue.isEmpty()) {
                leftQueue.offer(num);
            } else if (rightQueue.isEmpty()) {
                rightQueue.offer(num);
            }

            if (i == 1 && !leftQueue.isEmpty() && !rightQueue.isEmpty()
                    && leftQueue.peek() > rightQueue.peek()) {
                int temp = leftQueue.poll();
                leftQueue.offer(rightQueue.poll());
                rightQueue.offer(temp);
            }

            if (!leftQueue.isEmpty() && !rightQueue.isEmpty()) {
                if (leftQueue.size() < rightQueue.size()) {
                    int temp = leftQueue.poll();
                    leftQueue.offer(rightQueue.poll());
                    rightQueue.offer(temp);
                } else if (leftQueue.size() > rightQueue.size()) {
                    int temp = rightQueue.poll();
                    rightQueue.offer(leftQueue.poll());
                    leftQueue.offer(temp);
                }
            }

            if (i >= 2 && !leftQueue.isEmpty() && !rightQueue.isEmpty()) {
                if (leftQueue.peek() > num) {
                    leftQueue.offer(num);
                } else if (rightQueue.peek() < num) {
                    rightQueue.offer(num);
                } else if (leftQueue.peek() <= num && rightQueue.peek() >= num) {
                    if (leftQueue.size() <= rightQueue.size()) {
                        leftQueue.offer(num);
                    } else {
                        rightQueue.offer(num);
                    }
                }
            }
            sb.append(leftQueue.peek()).append("\n");
        }

        System.out.println(sb);
    }
}

이렇게 만들어봤는데

큐에 들어간 숫자가 정렬되는 기준을 모르겠다...

분명히 이전 코드에서는 큐를 출력했을 때 정렬된 큐가 나온 것 같았는데 새로 만든 큐는 수가 뒤죽박죽이다.

잘 모르겠다 다음에 수정해야겠다.