[Java] 백준 31792 - 한빛미디어 (Hard)

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

문제

---

풀이

삽입/삭제/탐색 모두 시간 복잡도 O(logN)에 가능한 이진 탐색 트리를 활용할 수 있다.

질의 3 (탐색) 같은 경우 그리디하게 접근할 수 있는데, 그냥 가격이 낮은 책부터 진열하다가 새로운 페이지가 필요하면 추가하면 된다. 물론 하나하나씩 탐색하면 O(N)이 되므로 S = S * 2  같은 식으로 탐색하기. (TreeMap.higerKey(Key k) 메서드를 활용하면 쉬움) 

---

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int Q = Integer.parseInt(br.readLine());
		TreeMap<Integer, Integer> map = new TreeMap<>();

		while (Q-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int cmd, S;
			cmd = Integer.parseInt(st.nextToken());

			switch (cmd) {
			case 1:
				S = Integer.parseInt(st.nextToken());
				map.put(S, map.getOrDefault(S, 0) + 1);
				break;
			case 2:
				S = Integer.parseInt(st.nextToken());
				if (map.containsKey(S)) {
					map.put(S, map.get(S) - 1);
					if (map.get(S) == 0) {
						map.remove(S);
					}
				}
				break;
			case 3:
				int pageCnt = 0;
				if (map.size() > 0) {
					Integer curS = map.firstKey();
					pageCnt++;

					while ((curS = map.higherKey(curS * 2 - 1)) != null) {
						pageCnt++;
					}
				}
				sb.append(pageCnt).append('\n');
				break;
			}
		}

		System.out.println(sb);
		br.close();
	}
}