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

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

7662번: 이중 우선순위 큐

 

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

이중 우선순위 큐란 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 

 

일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

 

시간제한 : 6초

 

 

2. 나의 방식대로 문제를 재정의 하자.

이중 우선순위 큐란 우선순위 큐에 deque의 개념이 합쳐진 것이다.

우선순위가 가장 높은, 가장 낮은 데이터를 삽입,삭제하는 연산을 수행하는 자료구조를 완성하는 문제.

 

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

문제에 쓰이는 자료구조에 대한 이해가 부족해서 굉장히 오래걸린 문제이다.

 

처음에는 ArrayList<Integer>에 오름차순 정렬을 하고, 가장 큰 인덱스값과 인덱스 0값을 통해 최소, 최댓값을 계산했다.

하지만 정렬 과정에서 Collections.sort(); 함수를 사용했고, 시간복잡도 O(n log n)으로 시간초과가 발생했다.

 

그래서 2가지의 자료구조를 이용했다.

 

 

1. 두개의 우선순위 큐

	Map<Integer, Integer> map = new HashMap<>();
	PriorityQueue<Integer> minQue = new PriorityQueue<>();
	PriorityQueue<Integer> maxQue = new PriorityQueue<>(Collections.reverseOrder());

위와 같이 오름차순, 내림차순 정렬을 각각 생성하고, map에 데이터 값의 갯수를 저장한다.

 

insert에는 두개의 큐에 모두 값을 저장하여 정렬시키고, 

delete할 때에는 최대값 제거 시 maxQue의 값을 제거하되, map에 1개이상 있을 경우에만 제거하도록 한다.

map에 해당하는 데이터가 없을 경우에는 이미 minQue에서 삭제한 경우이므로, maxQue에서 제거하고, 다음 값을 다시 제거 시도한다.

 

 

 

2. TreeMap 사용

    TreeMap<Integer, Integer> map = new TreeMap<>();
    map.lastKey(); //max
    map.firstKey(); //min

다음은 java에서 제공하는 TreeMap을 사용하는 것이다.

 

이번에 처음 접한 자료구조인데, 이걸 사용하면 최소, 최댓값을 찾는데 O(log n)이 걸리는 아주 좋은 성능을 가지고 있다.

min-max heap 사용에 어려움을 겪었는데, 이와 유사하게 사용할 수 있는 자료구조인 것 같아 앞으로 꼭 기억해두면 좋을 것 같다.

 

TreeMap 이용시 1번보다 연산이 훨씬 간단해진다. 

insert는 map.put()을 통해 넣으면 정렬되고

delete할 때도 마찬가지로 최댓값 최솟값에 따라 가장 크거나 작은 값을 map.remove()한다.

 

 

4. 어떻게 계산할 것인가?

1) 입력

BufferedReader

StringTokenizer

 

 

2) 시간 복잡도 계산

O(n log n)

 

 

5. 주의할 점은 무엇인가?

시간초과에 주의하기

 

 

6. 풀이 과정

 

1. 두개의 우선순위 큐 이용

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

public class q7662 {
  static private BufferedReader br;
  static private StringTokenizer st;
  static private String method;
  static private Integer value;
  static private Integer calc;
  public static void main(String[] args) throws IOException {
    br = new BufferedReader(new InputStreamReader(System.in));
    Integer testCase = Integer.parseInt(br.readLine());

    for (int tc = 0; tc < testCase; tc++) {
      solution();
    }

    br.close();
  }

  
  private static void solution() throws IOException {
    Map<Integer, Integer> map = new HashMap<>();
    PriorityQueue<Integer> minQue = new PriorityQueue<>();
    PriorityQueue<Integer> maxQue = new PriorityQueue<>(Collections.reverseOrder());

    calc = Integer.parseInt(br.readLine());

    for (int i = 0; i < calc; i++) {
      st = new StringTokenizer(br.readLine());
      method = st.nextToken();
      value = Integer.parseInt(st.nextToken());

      if (method.equals("I")) {

        map.put(value, map.getOrDefault(value, 0) + 1);
        minQue.add(value);
        maxQue.add(value);

      } else if (method.equals("D")) {
        if (map.size() == 0) {
          continue;
        }

        PriorityQueue<Integer> que = value == 1 ? maxQue : minQue;
        removeMap(que, map);
      }
    }

    if (map.size() == 0) {
      System.out.println("EMPTY");
    } else {
      int max = removeMap(maxQue, map);
      System.out.println(max + " " + (map.size() > 0 ? removeMap(minQue, map) : max));
    }

  }

  static int removeMap(PriorityQueue<Integer> que, Map<Integer, Integer> map) {
    int num;
    while (true) {
      num = que.poll();
      int cnt = map.getOrDefault(num, 0);

      if (cnt == 0)
        continue;

      if (cnt == 1)
        map.remove(num);
      else
        map.put(num, cnt - 1);

      break;
    }

    return num;
  }
  
}

 

 

2. TreeMap 이용

 

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

public class q7662 {
  static private BufferedReader br;
  static private StringTokenizer st;
  static private String method;
  static private Integer value;
  static private Integer calc;
  public static void main(String[] args) throws IOException {
    br = new BufferedReader(new InputStreamReader(System.in));
    Integer testCase = Integer.parseInt(br.readLine());

    for (int tc = 0; tc < testCase; tc++) {
      solution();
    }

    br.close();
  }
  
  private static void solution() throws IOException {
    TreeMap<Integer, Integer> map = new TreeMap<>();

    calc = Integer.parseInt(br.readLine());

    for (int i = 0; i < calc; i++) {
      st = new StringTokenizer(br.readLine());
      method = st.nextToken();
      value = Integer.parseInt(st.nextToken());

      if (method.equals("I")) {

        map.put(value, map.getOrDefault(value, 0) + 1);

      } else if (method.equals("D")) {
        if (map.size() == 0) {
          continue;
        }

        int num = value == 1 ? map.lastKey() : map.firstKey();
        map.put(num, map.get(num) - 1);
        if (map.get(num) == 0) {
          map.remove(num);
        }
      }
    }

    if (map.size() == 0) {
      System.out.println("EMPTY");
    } else {
      int max = map.lastKey();
      System.out.println(max + " " + (map.size() > 0 ? map.firstKey(): max));
    }

  }

  
}

 

 

 

7. 개선점

자료구조에 대한 지식이 많이 부족하다. 앞으로 조금씩 정리해야 될 것 같다.