[JAVA] BOJ(백준) - 이중 우선순위 큐 - 7662

문제 내용

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

7662번: 이중 우선순위 큐

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

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. 

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

입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적용할 연산의 개수를 나타내는 정수 k (k ≤ 1,000,000)가 주어진다. 이어지는 k 줄 각각엔 연산을 나타내는 문자(‘D’ 또는 ‘I’)와 정수 n이 주어진다. ‘I n’은 정수 n을 Q에 삽입하는 연산을 의미한다. 동일한 정수가 삽입될 수 있음을 참고하기 바란다. ‘D 1’는 Q에서 최댓값을 삭제하는 연산을 의미하며, ‘D -1’는 Q 에서 최솟값을 삭제하는 연산을 의미한다. 최댓값(최솟값)을 삭제하는 연산에서 최댓값(최솟값)이 둘 이상인 경우, 하나만 삭제됨을 유념하기 바란다.

만약 Q가 비어있는데 적용할 연산이 ‘D’라면 이 연산은 무시해도 좋다. Q에 저장될 모든 정수는 32-비트 정수이다. 

출력

출력은 표준출력을 사용한다. 각 테스트 데이터에 대해, 모든 연산을 처리한 후 Q에 남아 있는 값 중 최댓값과 최솟값을 출력하라. 두 값은 한 줄에 출력하되 하나의 공백으로 구분하라. 만약 Q가 비어있다면 ‘EMPTY’를 출력하라.

 

---

문제 접근 방법

총 3가지 방법으로 접근했다.

1. PriorityQueue를 두번 사용.(시간 초과)

2. LinkedList와 Collections.sort 사용.(시간 초과)

3. TreeMap 사용.(성공)

 

위의 3가지 방법으로 접근했고 결과적으론 3가지 모두 로직은 맞다. 하지만 시간복잡도 부분에서 TreeMap을 사용한 풀이만 시간내에 통과하게 됐다.

그래서 일단 세가지 방법에 대해 말해보려 한다.

 

첫번째(PriorityQueue)

PriorityQueue를 사용할때 로직은 아래와 같이 생각했다.

• PriorityQueue를 두가지 사용한 이유
  "D" 입력이 들어왔을때 뒤의 -1, 1 숫자에 따라서 값을 다르게하여 삭제해야 하기 때문에
  오름차순으로 PriorityQueue<Integer> upQ 하나
  내림차순으로 PriorityQueue<Integer> downQ 하나
  총 두개의 PriorityQueue가 필요하다고 생각하여 두가지를 사용했다.
• 입력값에 "I" 가 나왔을때
  "I"가 나왔을때 뒤에 있는 값(숫자)를 위에서 선언했던 두개의 우선순위 큐에 add 해준다.
  
  
• 입력값에 "D"가 나왔을때
  "D"가 나왔을때 뒤에 있는 값이 -1 이라면 최솟값을 삭제해야 한다.
  따라서 upQ에 있는 제일 앞의값을 삭제후 downQ에서 그값에 똑같이 해당하는 값을 지워준다.
  즉, temp = upQ.poll() 실행 후 downQ.remove(temp) 가된다.
  
  반대로 1 이라면 최대값을 삭제해야 한다.
  따라서 downQ에 있는 제일 앞의값을 삭제후 upQ에서 그값에 똑같이 해당하는 값을 지워준다.
  즉, temp = downQ.poll() 실행 후 upQ.remove(temp) 가된다.
  
• 결과
  입력받은 데이터만큼 위의 로직대로 실행시킨후 큐에 남아있는 숫자에 따라
  "EMPTY" , "최대+" "+최소" 를 출력해준다.
  
  
• 실패
  실패한 이유는 시간초과이다. 이때 테스트 케이스를 제외하고 시간복잡도를 계산하면
  입력받는 데이터 수 만큼 위의 로직 반복하는 시간: n
  PriorityQueue에서 메서드 remove를 실행하는 시간: n
  전체 로직의 시간복잡도 : O(N^2)
  (참고: PriorityQueue는 heap으로 구현돼있기 때문에 poll, add같은 메서드를 실행할땐 logN 이 걸림)

 

두번째(LinkedList와 Collections.sort)

• LinkedList를 사용한 이유
  큐를 두번 사용하지 않고 list하나를 활용해서 입력받은 값에대해
  list에 추가하는 값을 오름차순으로 정렬시키고 최대, 최소를 삭제시켜주기 위해서
  사용했다.
  
  
• 입력값 "I"가 나왔을때
  "I" 가 나왔을때 list에 추가 후 Collections.sort()를 활용해 list를 정렬 시킨다.
  
  
• 입력갑 "D"가 나왔을때
  -1 일때
  오름차순 정렬된 list에서 최솟값을 뽑는다. 즉, list.poll() 을 실행한다.
  
  1 일때
  오름차순 정렬된 list에서 최대값을 뽑는다. 즉, list.pollLast() 을 실행한다.
  
  
• 결과
  입력받은 데이터만큼 위의 로직대로 실행시킨후 list에 남아있는 숫자에 따라
  "EMPTY" , "최대+" "+최소" 를 출력해준다.
  
  
• 실패
  마찬가지로 시간초과로 실패했다. 시간복잡도를 계산하면 아래와 같다.
  입력받는 데이터 수 만큼 위의 로직 반복하는 시간: N
  list정렬시 사용하는 Collections.sort의 시간: NlogN
  전체 로직의 시간복잡도 : O(N^2logN)
  
  
• 참고
  Collections.sort() -> 평균/최악: O(NlogN)
  Arrays.sort() -> 평균: O(NlogN) / 최악: O(N^2)
  결과는 같지만 시간복잡도 차이나는 이유는 정렬시 사용하는 알고리즘이 다름.
  
  Collections.sort() -> TimeSort (삽입정렬과 합병정렬을 결합한 정렬) 사용
  Arrays.sor() -> DualPivotQuicksort 사용

 

세번째(TreeMap)

• TreeMap을 사용한 이유
  TreeMap은 원소 추가, 삭제할때 자동으로 정렬시켜준다.
  그리고 key와 value를 이용해 중복된 입력데이터에 대해 비교적 쉽게 처리할 수 있다.
  
  
• 입력값 "I"가 나왔을때
  "I" 일때 들어온 값을 key값으로 하여 TreeMap에 추가해준다.
  이때 getOrDefault 메서드를 이용해 현재 탐색중인 key값에 대해
  기존에 값이 있다면 value에 -> 기존값 + 1
  기존에 값이 없다면 value에 - > 1
  을 추가해준다.
  
  
• 입력값 "D"가 나왔을때
  -1 일때
  가장앞의 key값을 뽑고 value를 확인한다.
  value가 1보다 크다면 똑같은 정수가 여러번 입력된 의미로 value값을 -1 시켜준다.
  value가 1이면 해당 정수는 한번 입력된것으로 Map에서 삭제 시켜준다.
  
  1 일때
  가장뒤의 key값을 뽑고 value를 확인한다.
  value가 1보다 크다면 똑같은 정수가 여러번 입력된 의미로 value값을 -1 시켜준다.
  value가 1이면 해당 정수는 한번 입력된것으로 Map에서 삭제 시켜준다.
  
  
• 결과
  입력받은 데이터만큼 위의 로직대로 실행시킨후 Map에 남아있는 숫자에 따라
  "EMPTY" , "최대+" "+최소" 를 출력해준다.
  
  
• 성공
  이번엔 시간초과가 안떴다. 시간복잡도를 보면 알수 있다.
  입력받는 데이터 수 만큼 위의 로직 반복하는 시간: N
  TreeMap에 원소 추가, 삭제, get, 정렬 하는 시간: lonN
  전체 로직의 시간복잡도 : O(NlogN)
  
  
• 참고
  TreeMap의 get,삽입,삭제,정렬 모두 포함해서 logN의 시간이 걸린다.

 

위의 3가지 풀이를 보면 알겠지만 로직은 모두 같다.
다만 시간 복잡도차이가 날뿐...

 

자세한 풀이는 코드를 보자

---

풀이

첫번째(PriorityQueue)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i=0; i<N; i++) {
			int k = Integer.parseInt(br.readLine());
			String[] arr = new String[k];
			int[] value = new int[k];
			for(int j=0; j<k; j++) {
				st = new StringTokenizer(br.readLine());
				arr[j] = st.nextToken();
				value[j] = Integer.parseInt(st.nextToken());
			}
			System.out.println(queue(arr, value));
		}
	}
	
	public static String queue(String[] arr, int[] value) {
		PriorityQueue<Integer> upQ = new PriorityQueue<Integer>();
		PriorityQueue<Integer> downQ = new PriorityQueue<Integer>(Collections.reverseOrder());
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		for(int i=0; i<arr.length; i++) {
			int temp = 0;
			if(arr[i].equals("I")) {
				upQ.add(value[i]);
				downQ.add(value[i]);
			}else {
				if(downQ.size()==0) continue;
				if(value[i]==1) {
					temp = downQ.poll();
					upQ.remove(temp);
				}else {
					temp = upQ.poll();
					downQ.remove(temp);
				}
			}
		}

		if(upQ.size()==0) {
			return "EMPTY";
		}else if(upQ.size()==1 || downQ.size()==1) {
			min = upQ.poll();
			max = min;
		}else {
			min = upQ.poll();
			max = downQ.poll();
		}
		
		return max+" "+min; 
	}
}

 

두번째(LinkedList와 Collections.sort)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i=0; i<N; i++) {
			int k = Integer.parseInt(br.readLine());
			String[] arr = new String[k];
			int[] value = new int[k];
			for(int j=0; j<k; j++) {
				st = new StringTokenizer(br.readLine());
				arr[j] = st.nextToken();
				value[j] = Integer.parseInt(st.nextToken());
			}
			System.out.println(queue(arr, value));
		}
	}
	
	public static String queue(String[] arr, int[] value) {
		LinkedList<Integer> list = new LinkedList<>();
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		for(int i=0; i<arr.length; i++) {
			if(arr[i].equals("I")) {
				list.add(value[i]);
				Collections.sort(list, new Comparator<Integer>() {

					@Override
					public int compare(Integer o1, Integer o2) {
						if(o1 > o2) return 1;
						else if(o1 < o2) return -1;
						else return 0;
					}
				});
			}else {
				if(list.size()==0) continue;
				if(value[i]==-1) {
					list.poll();
				}else {
					list.pollLast();
				}
			}
		}

		if(list.size()==0) {
			return "EMPTY";
		}else if(list.size()==1) {
			min = list.poll();
			max = min;
		}else {
			min = list.poll();
			max = list.pollLast();
		}
		
		return max+" "+min; 
	}
}

 

세번째(TreeMap)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i=0; i<N; i++) {
			int k = Integer.parseInt(br.readLine());
			String[] arr = new String[k];
			int[] value = new int[k];
			for(int j=0; j<k; j++) {
				st = new StringTokenizer(br.readLine());
				arr[j] = st.nextToken();//"I" , "D" 
				value[j] = Integer.parseInt(st.nextToken());//값
			}
			System.out.println(queue(arr, value));
		}
	}
	
	public static String queue(String[] arr, int[] value) {
		//key=값, value=값의 갯수, TreeMap은 자동 정렬됨.
		TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		for(int i=0; i<arr.length; i++) {
			if(arr[i].equals("I")) {
				//삽입, 삽입 시 key값이 존재하면 value+1 하고 아니면 걍 1
				map.put(value[i], map.getOrDefault(value[i], 0)+1);
			}else {
				if(map.isEmpty()) continue;//map비었으면 무시
				if(value[i]==-1) {//최솟값
					//맨앞에 값(최소)
					int key = map.firstKey();
					//해당 key값의 value가 여러개면 하나 줄이기(삭제)
					if(map.get(key)>1) map.put(key, map.get(key)-1);
					//value가 1이면 걍 key값 삭제
					else map.remove(key);
				}else {
					//맨뒤에 값(최대)
					int key = map.lastKey();
					//해당 key값의 value가 여러개면 하나 줄이기(삭제)
					if(map.get(key)>1) map.put(key, map.get(key)-1);
					//value가 1이면 걍 key값 삭제
					else map.remove(key);
				}
			}
		}

		if(map.isEmpty()) {//map이 비었으면
			return "EMPTY";
		}else if(map.size()==1) {//map의 key개수가 1개이면
			min = map.firstKey();
			max = min;
		}else {//map의 key개수가 여러개 일때
			min = map.firstKey();
			max = map.lastKey();
		}
		
		return max+" "+min; 
	}
}

---

마치며

로직은 어렵지 않으나.. 시간복잡도를 유의하고 풀어야하는 문제였다.

그래서 이번에 내가 사용하던 메서드들의 시간복잡도를 알아볼수 있는 기회가 됐다.