[ 백준 ] 7662 이중 우선순위 큐

codesver·2022년 12월 17일
0

Baekjoon

목록 보기
35/72
post-thumbnail

Analyze

하나의 해결 방법은 Priority Queue를 사용하는 것이다.

아래의 코드는 하나의 테스트에 대한 해결 방법이다.

StringTokenizer tokenizer;
Queue<Integer> min = new PriorityQueue<>();
Queue<Integer> max = new PriorityQueue<>(Comparator.comparingInt(o -> -o));

int operationNum = Integer.parseInt(reader.readLine());
while (operationNum-- > 0) {
    tokenizer = new StringTokenizer(reader.readLine());
    if (tokenizer.nextToken().equals("I")) {
        int data = Integer.parseInt(tokenizer.nextToken());
        min.add(data);
        max.add(data);
    } else if (Integer.parseInt(tokenizer.nextToken()) == 1 && 
    				!max.isEmpty()) min.remove(max.poll());
    else if (!min.isEmpty()) max.remove(min.poll());
}

result.append(max.isEmpty() ? "EMPTY" : max.peek() + " " + min.peek()).append("\n");

min queue는 오름차순이고 max queue는 내림차순이다.

Operation이 I이면 max와 min queue에 단순 삽입한다.

Operation이 D이면 삭제 연산을 실행한다.

이때 operation type이 1이면 max 값을 각각의 queue에서 제거한다.

반대로 operation type이 -1이면 min 값을 각각의 queue에서 제거한다.

위와 같은 방법으로 문제를 해결할 수는 있으나 문제에서 주어진 제한시간은 지키지 못한다.

제거 연산마다의 queue.remove() 연산이 추가되기 때문으로 생각한다.


이를 해결하기 위해 TreeMap을 사용할 수 있다.

TreeMap은 이진트리를 기반으로 하는 Map collection이다.

삭제/삽입 연산에 있어서 HashMap보다는 비효율적이지만 TreeMap은 자동 정렬이 된다.

최대/최소값을 알아야하는 문제 특성상 TreeMap을 사용한다.

Solution

private static void solution() throws IOException {
    int T = Integer.parseInt(reader.readLine());
    while (T-- > 0) {
        TreeMap<Integer, Integer> Q = new TreeMap<>();
        StringTokenizer tokenizer;

        int operations = Integer.parseInt(reader.readLine());
        while (operations-- > 0) {
            tokenizer = new StringTokenizer(reader.readLine());
            if (tokenizer.nextToken().equals("I"))
                Q.merge(Integer.parseInt(tokenizer.nextToken()), 1, Integer::sum);
            else if (!Q.isEmpty()) {
                Integer data = Integer.parseInt(tokenizer.nextToken()) == 1 ?
                        Q.lastKey() :
                        Q.firstKey();
                if (Q.get(data) > 1) Q.merge(data, -1, Integer::sum);
                else Q.remove(data);
            }
        }

        result.append(Q.isEmpty() ? "EMPTY" : Q.lastKey() + " " + Q.firstKey())
                .append("\n");
    }
}
profile
Hello, Devs!

0개의 댓글