하나의 해결 방법은 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을 사용한다.
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");
}
}