[백준] Q7662 이중 우선순위 큐 JAVA

[백준] Q7662 이중 우선순위 큐 JAVA

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

접근 방법

'자료구조 구현 문제'라고 생각했다. 유사한 자료구조를 책에서 본 기억이 났지만 정확하게 생각나지 않았고 문제를 푼 후에 찾아보았다.

결국 자료구조 구현 문제이기 때문에 어떻게 자료를 관리할지에 대한 고민을 하게 된다.

1. 우선순위 큐를 2개 사용하여 순서를 보장하고, Map을 통해 데이터 개수를 관리하는 방법

2. Binary Search Tree

3. SMMH Interval Heap

으로 생각했다.

구현 내용

1. 우선순위 큐 2개 + Map

Naiive하게 접근한다. 최소 최대에 따른 우선순위를 저장할 큐를 두개 사용한다.

이 때, 큐는 데이터를 관리보다는 우선순위에 초점을 맞추고 실질적인 데이터의 관리는 Map을 통해 관리하게 된다.

1.1 Insert

데이터의 관리를 Map으로 관리하므로 들어오는 값에 대해 개수를 카운팅하고 각각의 큐에 삽입한다.

1.2 Delete

데이터가 삭제 될 때 (map.get(data)-1 == 0) 데이터를 관리하는 map에서 제거한다.

또한 큐에서는 해당 데이터가 실제 존재하는지 아닌지를 map을 통해 추적하여 삭제 또는 업데이트 해준다.

1.3 Max, Min, Print, Empty

data의 관리를 map에서 관리하고 있기 때문에 map의 사이즈가 0일 경우 EMPTY 이다.

EMPTY가 아닐 경우 데이터가 존재한다는 뜻으로 print해야하는 순서에 맞도록 maxQ에서 꺼내본다.

이 때, 정의해놓은 함수를 사용할 경우 map안에서 데이터가 삭제되어 데이터가 하나일 경우 minQ에서도 찾지 못하는 case가 생긴다. 이를 고려하여 min값을 구한다.

import java.io.*; import java.util.*; public class Main { static BufferedReader br; static StringBuilder sb; public static void main(String[] args) throws Exception { br = new BufferedReader(new InputStreamReader(System.in)); sb = new StringBuilder(); int T = Integer.parseInt(br.readLine()); while (T-- > 0) { solution(); } System.out.print(sb.toString()); } // PQ with Map // 우선순위를 PQ로 관리하고, Map으로 data들을 관리한다. public static void solution() throws IOException { PriorityQueue minQ = new PriorityQueue(); PriorityQueue maxQ = new PriorityQueue(Collections.reverseOrder()); Map dataInfo = new HashMap(); int N = Integer.parseInt(br.readLine()); StringTokenizer st; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); String cmd = st.nextToken(); int val = Integer.parseInt(st.nextToken()); switch (cmd) { case "I": minQ.add(val); maxQ.add(val); dataInfo.put(val, dataInfo.getOrDefault(val, 0) + 1); break; case "D": PriorityQueue q = val == 1 ? maxQ : minQ; removeData(q, dataInfo); break; } } // 8개들어올때 min 4개빼고 max 4개빼면 각각은 모두 있다. // empty가 아니다. // 생각을 잊지 말자 우리는 data를 dataInfo로 관리하기로 하였다. if (dataInfo.size() == 0) sb.append("EMPTY

"); else { int n = removeData(maxQ, dataInfo); sb.append(n).append(" ").append(dataInfo.size() > 0 ? removeData(minQ, dataInfo) : n).append('

'); } } public static int removeData(PriorityQueue q, Map map) { while (!q.isEmpty()) { int num = q.poll(); int numCnt = map.getOrDefault(num, 0); if (numCnt == 0) continue; if (numCnt == 1) { map.remove(num); // data없어짐. } else map.put(num, numCnt - 1); return num; } return 0; }

2. Binary Search Tree

이진탐색트리는 정렬된 이진트리이다. 이를 통해 가장 작은 값과 가장 큰 값을 빠르게 구할 수 있다.

하지만, 편향 트리의 경우 결국 배열을 사용하는 것과 마찬가지인 worst time complexity를 가지게 된다.

편향트리가 문제가 되는 것은 결국 높이가 깊어진다는 것인데 이러한 것을 낮추고 최적화하기 위한 여러 방법이 있는데 b+ , b-tree, red-black tree등등이 있다.

JAVA에서 TreeMap은 이진트리를 기반으로한 Map 컬렉션 중에서도 Sorted Map으로 정렬을 보장하고 있다.

또한 내부적으로 Red-Black Tree로 구현되어 있다.

이를 이용하면 효율적으로 최대값과 최소값을 구할 수 있다.

구현의 경우 TreeMap의 함수들을 사용하여 구현한다.

// TreeMap public void solution2() throws IOException { TreeMap map = new TreeMap<>(); StringTokenizer st; int k = Integer.parseInt(br.readLine()); for (int i = 0; i < k; i++) { st = new StringTokenizer(br.readLine()); String cmd = st.nextToken(); int val = Integer.parseInt(st.nextToken()); if (cmd.equals("I")) { map.merge(val, 1, Integer::sum); // ?? } else { if (map.isEmpty()) continue; int target = (val == 1) ? map.lastKey() : map.firstKey(); if (map.get(target) > 1) map.put(target, map.get(target) - 1); else map.remove(target); } } if (map.isEmpty()) sb.append("EMPTY

"); else sb.append(map.lastKey() + " " + map.firstKey() + "

"); }

여기서 map.merge(key, value, BiFunction)으로 사용하는데 merge의 설명을 보면

If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value. Otherwise, replaces the associated value with the results of the given remapping function, or removes if the result is null. This method may be of use when combining multiple mapped values for a key.

key와 관련된 값이 아직 없거나 null일 때 이를 non-null value로 관련지어준다. 또는 값을 remapping function을 통해 변경해주는 역할을 가지고 있다.

map.put(key, map.getOrDefault(key,0)+1) 로 해도 충분히 가능하지만 시간적으로 차이가 많이 났다.

코드 내부적으로 따라가보면 함수 호출이 적다.

Map interface에 default로 정의되어 있다.

default V merge(K key, V value, BiFunction remappingFunction) { Objects.requireNonNull(remappingFunction); Objects.requireNonNull(value); V oldValue = get(key); V newValue = (oldValue == null) ? value : remappingFunction.apply(oldValue, value); if (newValue == null) { remove(key); } else { put(key, newValue); } return newValue; }

마찬가지로 getOrDefault의 경우 같은 곳에 정의되어 있는데,

default V getOrDefault(Object key, V defaultValue) { V v; return (((v = get(key)) != null) || containsKey(key)) ? v : defaultValue; }

containsKey까지 확인하기 때문에 호출이 확실히 많았다.

3. SMMH(Symmetric Min Max Heap)과 Interval Heap

글을 쓰게 된 이유인데, 처음 문제를 보았을 때 가장 먼저 든 생각이다.

분명 비슷한 자료구조를 책에서 본 것 같고 세그먼트 트리와 같이 구간적으로 최소, 최대를 구하는 것이 있다고 생각했다.

https://gseok.gitbooks.io/algorithm/content/d2b8-b9ac-c54c-ace0-b9ac-c998/c138-adf8-ba3c-d2b8-d2b8-b9ac28-segment-tree.html(참조)

세그먼트 트리에 대해서는 추후 다룰 예정이다.

SMMH는 다음과 같은 모양을 가진다.

구간 힙은 다음과 같은 모양을 가진다.

두 힙 모두 완전 이진트리 형태로 빠르게 삽입 삭제를 할 수 있다.

SMMH의 성질

1. 각 노드의 원소는 오른쪽 형제 원소보다 작거나 같다.

2. 조부모를 가진 모든 노드 N에 대하여 조부모의 왼쪽 자식에 있는 N 보다 작거나 같다

3. 조부모를 가진 모든 노드 N에 대하여 조부모의 오른쪽 자식에 있는 N보다 크거나 같다.

구간 힙

각 노드가 두개의 원소(a,b $a<=b$)를 포함하고 있는 완전 이진트리이다.

각 노드는 닫힌 구간 [a,b]를 표현하며 각 노드의 자식은 범위 안에 포함된다.

노드 구간의 왼쪽 끝점을 최소 힙, 오른쪽 끝점은 최대 힙으로 볼 수 있다.

우선순위 큐들과 관련된 심화 내용은 여기서 확인할 수 있다.

실제 구현하는 것 보다 TreeMap을 통해 빠르게 해결할 수 있었고 이후에 비슷한 문제를 만나게 되면 구현해 볼 예정이다.

from http://sogogi486.tistory.com/24 by ccl(A) rewrite - 2021-12-07 02:00:38