BOJ G4 7662 이중 우선순위 큐 JAVA

7662번: 이중 우선순위 큐

---

문제 읽기

처음 문제를 읽었을 때는 시간 제한이 6초이고, T의 범위가 나와있지 않아서 좀 당황했었다.. 어쨌든 문제를 해결하려는데, 저번에 IOIOI를 풀었을 때처럼 한 번에 연산이 되는 게 아니라서 생각을 좀 했었다.

문제 풀이는 다음과 같은 과정을 통해 이루어졌다.

1. ArrayList 1개와 이진 삽입 정렬 - 시간 초과
2. 우선순위 큐 2개와 Map - OK
3. TreeMap 사용하기 - Good

---

문제 풀기

ArrayList 1개와 이진 삽입 정렬 - 잘못된 풀이

처음에는 리스트 하나만 사용하면서 이진 탐색을 활용해서 값을 입력하면서 삽입하는 방식을 생각했다. 과정을 정리해보면 다음과 같다.

1. cmd와 value를 입력받는다.
   1. 삽입이면 binary 탐색을 통해 들어갈 위치를 찾고, 해당 위치에 삽입한다. 즉, 리스트를 오름차순 형태로 유지한다.
   2. 최댓값 삭제이면, 리스트의 마지막 원소를 삭제한다.
   3. 최솟값 삭제이면, 리스트의 첫 번째 원소를 삭제한다.
2. 하나의 테스트 케이스가 끝나면 list에서 최댓값, 최솟값을 출력한다.

따라서 다음과 같이 코드를 작성했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static List<Integer> list;

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

        int T = Integer.parseInt(in.readLine());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int N = Integer.parseInt(in.readLine());

            list = new ArrayList<>();
            while (N-- > 0) {
                StringTokenizer st = new StringTokenizer(in.readLine());
                String cmd = st.nextToken();
                int value = Integer.parseInt(st.nextToken());

                if (cmd.equals("I")) {
                    //삽입
                    binaryInsert(value, 0, list.size());
                } else if (value == 1) {
                    //최댓값 삭제
                    if (!list.isEmpty()) list.remove(list.size() - 1); //마지막 원소 삭제
                } else {
                    //최솟값 삭제
                    if (!list.isEmpty()) list.remove(0);
                }
            }
            if (list.isEmpty()) {
                sb.append("EMPTY").append("\\n");
            } else {
                sb.append(list.get(list.size() - 1)).append(" ").append(list.get(0)).append("\\n");
            }
        }
        System.out.println(sb);
    }

    private static void binaryInsert(int value, int start, int end) {
        if (start >= end) {
            list.add(start, value);
            return;
        }
        int mid = (start + end) / 2;
        if (value < list.get(mid)) {
            binaryInsert(value, start, mid);
        } else {
            binaryInsert(value, mid + 1, end);
        }
    }

}

 

하지면 여기에 치명적인 문제가 있다.

 

binary 탐색을 하니까 logN만에 되겠지~ 했지만, 다음 과정을 다시 자세히 보자.

1. cmd와 value를 입력받는다.
   1. 삽입이면 binary 탐색을 통해 들어갈 위치를 찾고, 해당 위치에 삽입한다. 즉, 리스트를 오름차순 형태로 유지한다.
   2. 최댓값 삭제이면, 리스트의 마지막 원소를 삭제한다.
   3. 최솟값 삭제이면, 리스트의 첫 번째 원소를 삭제한다.
2. 하나의 테스트 케이스가 끝나면 list에서 최댓값, 최솟값을 출력한다.

리스트에서 원소를 삭제할 때는 O(1)의 시간복잡도이다. 또한 일반적인 삽입 방법인 add()를 활용한 삽입에도 O(1)의 시간복잡도를 가진다.

 

하지만, 여기서는 특정 인덱스에 원소를 삽입해야 하는데, ArrayList에서 이 경우의 시간 복잡도는 O(N)이다. 왜냐하면 특정 인덱스에 데이터를 삽입한 후 뒤에 있는 데이터를 한 칸씩 밀어주어야 하기 때문이다. 즉, 실컷 이진 탐색으로 위치를 찾아도 삽입할 때의 시간 복잡도 때문에 무용지물이 되어버린다..

 

시간 복잡도는 아래 포스팅을 참고했다.

java ArrayList, LinkedList

 

우선순위 큐 두 개와 Map

 

다음으로는 풀이를 찾아봤고, 오름차순, 내림차순으로 정렬된 우선순위 큐 두 개 minQ, maxQ와, 입력된 원소의 종류와 개수를 저장하는 Map을 활용하는 방식을 알게 되었다. 풀이 과정을 정리하면 다음과 같다.

1. cmd와 value를 입력받는다.
   1. 삽입이면
      1. map에 원소의 종류와 개수를 업데이트한다.
      2. minQ, maxQ에 삽입한다.
   2. 최댓값 삭제이면, maxQ에서 삭제되지 않은 원소 중 가장 큰 원소를 삭제한다.
      1. maxQ에서 값을 하나씩 꺼내면서, map에 있는 원소이면, 즉 아직 삭제되지 않은 원소이면 map의 원소 개수를 감소시켜 업데이트한다. map에 없다는 건 이미 삭제되었다는 뜻이다.
   3. 최솟값 삭제이면, minQ에서 삭제되지 않은 원소 중 가장 작은 원소를 삭제한다.
      1. 최댓값 삭제와 같은 원리이다.
2. 하나의 테스트 케이스가 끝나면 Q에서 최댓값, 최솟값을 출력한다. 물론 삭제되지 않은 값이어야 한다.

여기서 map을 쓰는 이유는, 하나의 입력들에 대해서 minQ, maxQ를 두 개 사용하기 때문에, maxQ에서 데이터를 지웠다면 minQ에서도 이를 알고 있어야 제대로된 최솟값과 최댓값을 출력할 수 있기 때문이다.

 

이를 고려해서 코드를 작성하면 다음과 같다.

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_G4_7662_이중우선순위큐 {

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

        int T = Integer.parseInt(in.readLine());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int N = Integer.parseInt(in.readLine());

            PriorityQueue<Integer> minQ = new PriorityQueue<>(); //디폴트는 오름차순 정렬이다.
            PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());

            Map<Integer, Integer> existMap = new HashMap<>(); //큐에 넣는 숫자마다 총 개수를 저장
            while (N-- > 0) {
                StringTokenizer st = new StringTokenizer(in.readLine());
                String cmd = st.nextToken();
                int value = Integer.parseInt(st.nextToken());

                if (cmd.equals("I")) {
                    //삽입
                    int cnt = existMap.getOrDefault(value, 0);
                    existMap.put(value, cnt+1);
                    maxQ.offer(value);
                    minQ.offer(value);
                } else if (value == 1) {
                    //최댓값 삭제
                    while(!maxQ.isEmpty()){
                        int removeVal = maxQ.poll();
                        if (existMap.containsKey(removeVal)){
                            //삭제된 원소가 아니라면
                            int cnt = existMap.get(removeVal);
                            if (cnt == 1) existMap.remove(removeVal);
                            else existMap.put(removeVal, cnt-1);
                            break;
                        }
                    }
                } else {
                    //최솟값 삭제
                    while(!minQ.isEmpty()){
                        int removeVal = minQ.poll();
                        if (existMap.containsKey(removeVal)){
                            //삭제된 원소가 아니라면
                            int cnt = existMap.get(removeVal);
                            if (cnt == 1) existMap.remove(removeVal);
                            else existMap.put(removeVal, cnt-1);
                            break;
                        }
                    }
                }
            }
            if (existMap.isEmpty()) {
                sb.append("EMPTY").append("\\n");
            } else {
                //최댓값 얻기
                while(!maxQ.isEmpty()){
                    int val = maxQ.poll();
                    if (existMap.containsKey(val)){
                        //삭제된 원소가 아니라면
                        sb.append(val).append(" ");
                        break;
                    }
                }
                //최솟값 얻기
                while(!minQ.isEmpty()){
                    int val = minQ.poll();
                    if (existMap.containsKey(val)){
                        //삭제된 원소가 아니라면
                        sb.append(val).append("\\n");
                        break;
                    }
                }
            }
        }
        System.out.println(sb);
    }

}

 

TreeMap 사용하기

 

TreeMap은 이진 트리를 기반으로 오름차순으로 정렬된 형태로 저장한다. 따라서 첫 번째 원소를 찾는 firstKey()와 마지막 원소를 찾는 lastKey()는 O(logN)밖에 소요되지 않는다.

 

즉 TreeMap만 사용하여 (입력 받은 원소, 개수)만 저장해주면 매우 쉽게 해결할 수 있다.

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_G4_7662_이중우선순위큐 {

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

        int T = Integer.parseInt(in.readLine());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int N = Integer.parseInt(in.readLine());
            TreeMap<Integer, Integer> treeMap = new TreeMap<>();
            while (N-- > 0) {
                StringTokenizer st = new StringTokenizer(in.readLine());
                String cmd = st.nextToken();
                int value = Integer.parseInt(st.nextToken());

                if (cmd.equals("I")) {
                    //삽입
                    treeMap.put(value, treeMap.getOrDefault(value, 0) + 1);
                } else {
                    if (treeMap.isEmpty()) continue;

                    int removeVal = (value == 1)? treeMap.lastKey() : treeMap.firstKey();
                    int cnt = treeMap.get(removeVal);

                    if (cnt == 1) treeMap.remove(removeVal); //이제 없어지면 삭제
                    else treeMap.put(removeVal, cnt-1);
                }
//                System.out.println(treeMap);
            }
            sb.append((treeMap.isEmpty())? "EMPTY\\n" : treeMap.lastKey() + " " + treeMap.firstKey() + "\\n");
        }
        System.out.println(sb);
    }

}

---

참고자료

[백준] 7662번: 이중 우선순위 큐 - JAVA