[자료구조2] 백준 7662 이중 우선순위 큐

7662번: 이중 우선순위 큐

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

 

# 코드

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

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

        // 테스트데이터의 수 T
        int t = Integer.parseInt(br.readLine());

        for (int i = 1; i <= t; i++) {
            int k = Integer.parseInt(br.readLine());

            // Map을 이용해 숫자와 해당 숫자의 개수를 저장
            // TreeMap : 이진트리를 기반으로 오름차순으로 정렬되는 Map
            TreeMap<Integer, Integer> q = new TreeMap<>();

            for (int j = 0; j < k; j++) {
                // 공백을 기준으로 입력문자열을 나눠 배열에 저장
                String[] input = br.readLine().split(" ");
                char ch = input[0].charAt(0);
                int n = Integer.parseInt(input[1]);

                // I, D에 따라 연산 처리
                if (ch == 'I') {
                    // q에 없는 키라면 개수를 0 + 1 로 하여 추가
                    // q에 있는 키라면 + 1 하여 해당 값을 대체
                    q.put(n, q.getOrDefault(n, 0) + 1);
                } else {
                    // q가 비어있는데 D 연산이 나오면 무시
                    if (q.size() == 0)
                        continue;

                    // q에 원소가 있을 경우
                    // 개수를 줄일 키인 num : n이 1이면 최댓값[laskKey()], 아니면 최솟값[firstKey()]
                    int num = n == 1 ? q.lastKey() : q.firstKey();

                    // num의 개수(value)를 1 감소시킨다.
                    // 만약 1이라면 Map에서 삭제시킴
                    if (q.put(num, q.get(num) - 1) == 1)
                        q.remove(num);
                }
            }

            // q가 비어있다면 EMPTY, 그렇지 않다면 최댓값과 최솟값을 출력한다.
            System.out.println(q.size() == 0 ? "EMPTY" : q.lastKey() + " " + q.firstKey());
        }

        // Reader 버퍼 닫기
        br.close();
    }
}

• TreeMap 은 이진트리를 기반으로 오름차순으로 정렬되어 저장되는 Map 자료구조이다.
• firstKey() : 가장 첫 번째 key, 즉 최솟값인 key를 반환하는 메소드
• lastKey() : 가장 마지막 key, 즉 최댓값인 key를 반환하는 메소드
• 기본적으로 Map의 key는 중복될 수 없다. 그렇기 때문에 개수를 value로 저장하는 방식으로 문제를 해결한다.

 

put VS. replace

put(K key, V value)

• 지정된 키와 값을 맵에 추가하거나 이미 존재하는 키의 현재 값을 새 값으로 대체
• 이전 값이 있었다면 그 값을 반환하고, 없었다면 null을 반환
• put은 키가 존재하든 그렇지 않든 값을 저장하거나 대체

replace(K key, V value)

• 지정된 키가 맵에 없으면 아무 것도 하지 않음
• 지정된 키가 이미 맵에 있을 경우 해당 키의 현재 값을 새 값으로 대체
• 이전 값이 있었다면 그 값을 반환하고, 없었다면 null을 반환
• replace는 맵에 키가 이미 존재해야만 값이 대체

 

따라서 결론은 다음과 같다.

• 데이터를 맵에 추가하거나 이미 존재하는 키의 값을 무조건 대체하려는 경우 → put
• 키가 이미 존재할 경우에만 값을 대체하려는 경우 → replace

 

 

자료구조를 무엇으로 써야할지 참 감이 안잡혔던 문제였다.

코드와 주석은 아래 블로그, put / replace 차이는 그 아래 블로그를 참고했다.

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

 

[Java]Map의 put과 replace 차이