[백준 7662]https://www.acmicpc.net/problem/7662
문제 조건
정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주한다.
Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력해야 한다.
이중 우선순위 큐에는 두 가지 연산이 있다.
1. 데이터를 삽입하는 연산
2. 데이터를 삭제하는 연산
2-1 우선순위가 가장 높은 것을 삭제하는 연산
2-2 우선순위가 가장 낮은 것을 삭제하는 연산
문제 입력
입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다.
각 테스트 데이터의 첫째 줄에는 Q에 적용할 연산의 개수를 나타내는 정수 k (k ≤ 1,000,000)가 주어진다.
이어지는 k 줄 각각엔 연산을 나타내는 문자(‘D’ 또는 ‘I’)와 정수 n이 주어진다.
'I n'은 정수 n을 Q에 삽입하는 연산. (동일한 정수 가능)
'D 1'은 Q에서 최댓값을 삭제하는 연산.
'D -1'은 Q에서 최솟값을 삭제하는 연산.
Q가 비어있는데 적용할 연산이 ‘D’라면 이 연산은 무시해도 좋다.
문제 풀기 전 설계
최댓값 또는 최솟값을 삭제해야 하기 때문에 최소, 최대 Heap 자료구조를 각각 사용해야 할 것 같다. Heap을 두 개를 사용하면서 한 쪽에서 삭제한 값이 다른 Heap에서도 삭제가 되어야 하는데 이 부분을 생각해 봐야 할 것 같다. 배열을 사용하기에는 입력받는 정수의 수가 정해져 있지 않고, map을 사용하기에는 정수를 키 값으로 받는다면 중복된 정수가 들어올 때 개수의 체크가 힘들다.
-> 그렇다면 정수를 입력 받을 때마다 map.containsKey 메소드로 확인해서 value 값으로 해당 정수의 개수를 저장하면 되지 않을까?
-> map을 사용한다면 굳이 PriorityQueue와 Hashmap을 사용하지 않고 레드-블랙 트리 구조인 Treemap을 사용하면 될 것 같다.
문제 코드
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));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine()); // 테스트케이스의 개수
for (int i = 0; i < t; i++) {
int k = Integer.parseInt(br.readLine()); // 연산의 개수
TreeMap<Integer, Integer> map = new TreeMap<>(); // 이중 우선순위 큐 역할을 할 TreeMap
for (int j = 0; j < k; j++) {
st = new StringTokenizer(br.readLine(), " ");
char cmd = st.nextToken().charAt(0); // 연산 명령을 구분하는 변수
int value = Integer.parseInt(st.nextToken()); // 연산 명령에 따라 삽입/삭제할 값
if (cmd == 'I') { // 삽입 연산
// TreeMap이 입력받은 정수를 갖고 있다면 그 value값에 + 1, 그렇지 않다면 1을 삽입
map.put(value, map.getOrDefault(value, 0) + 1);
}
else { // 삭제 연산
if (map.isEmpty()) continue; // TreeMap이 비어있다면 연산 X
else {
// TreeMap이 제공하는 firstKey()와 lastKey() 이용
int n = (value == 1) ? map.lastKey() : map.firstKey();
if (map.put(n, map.get(n) - 1) == 1) { // 해당 정수의 개수를 -1 해주면서 만약 0개가 된다면 삭제
map.remove(n);
}
}
}
}
if (map.isEmpty()) sb.append("EMPTY").append('\n'); // TreeMap이 비어있으면 "EMPTY" 저장
else sb.append(map.lastKey()).append(' ').append(map.firstKey()).append('\n'); // 그렇지 않다면 최솟값, 최댓값 저장
}
System.out.println(sb);
}
}문제 풀이
내부 구조가 레드-블랙 트리인 TreeMap을 이용해서 문제를 풀었는데, 입력이 들어오면 연산 명령을 구분하고, 만약 삽입 연산이라면 TreeMap에 그 정수가 있는지 비교해서 있다면 기존의 value에 값을 +1해주고, 그렇지 않다면 입력받은 정수를 key로 1의 value를 갖는 값을 넣어준다.
삭제 연산이라면 TreeMap의 정렬이 오름차순이기 때문에 입력 값이 1이라면 lastKey(), 그렇지 않다면 firstKey() 메소드를 실행한다.
k개의 연산이 모두 끝나면 TreeMap이 비어 있는지 체크해서 적절한 값을 출력한다.
Review
이 문제를 풀면서 Map과 관련된 메소드를 많이 알게 됐다. 특히 getOrDefault()라는 메소드는 Map을 사용한 여러 문제를 풀어보면서 처음 사용해봤다. 처음에는 최소 힙과 최대 힙 두 개와 하나의 Map으로 문제를 풀었는데, Map의 종류중에 이진 트리 구조인 TreeMap이 있다는 게 나중에 생각나서 TreeMap을 이용해서 풀었더니 기존 방식보다 훨씬 빠르고 간결하게 풀렸다. 역시 아는 것이 힘이라는 걸 다시 한번 마음에 새겼다.
