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

 

문제풀이

이 문제는 2가지 방법으로 풀 수 있다.

첫번째는 TreeMap이고, 두번째는 우선순위 큐를 2개 사용하는 것이다.

 

TreeMap부터 설명하겠다.

 

풀이 - TreeMap

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(bf.readLine());

    int T = Integer.parseInt(st.nextToken());
    for(int t=0; t<T; t++) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int Q = Integer.parseInt(bf.readLine());
        for(int q=0; q<Q; q++) {
            st = new StringTokenizer(bf.readLine());
            String input = st.nextToken();
            int num =Integer.parseInt(st.nextToken());

1. 문제에서 주어진 입력을 받을 코드를 작성한다.

이때 treeMap을 만들어준다.

Key와 Value는 모두 정수형이다.

 

if(input.equals("I")) {
    map.put(num, map.getOrDefault(num, 0) + 1);
}else {
    if(map.size() == 0) continue;

    int n;
    if(num == 1) {
        n = map.lastKey();
    }else {
        n = map.firstKey();
    }
    if(map.put(n, map.get(n)-1)==1) {
        map.remove(n);
    }
}

2. input에 해당하는 값(I 또는 D)가 I 인지, D 인지에 따라 조건을 나뉘어준다.

만약 input이 I 라면 TreeMap에 삽입한다.

 

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

여기서 num 값이 key가 되는데

입력에서

I 5

I 5 이 주어진다면 key가 중복으로 등록될 수 없으니 value 값을 1 증가시킨다.

 

if(map.size() == 0) continue;

만약 input이 D 라면 TreeMap에서 삭제한다.

그런데 문제에서  '비어있는데 적용할 연산이 'D'라면 이 연산은 무시해도 좋다고 했다' 라고 주어져있다.

그렇기 때문에 map에서 삭제할 값이 없는 상태 즉, 비어있는 상태일 때 D가 주어질 수도 있는 것이다.

이 오류를 막기 위해서 map의 사이즈가 0이라면 continue 한다.

 

int n;
if(num == 1) {
    n = map.lastKey();
}else {
    n = map.firstKey();
}

다음 코드를 보자.

num이 1이라면 최댓값을 삭제하고, num이 -1이라면 최솟값을 삭제한다.

 

TreeMap은 기본적으로 key에 대해 오름차순 정렬이다.

 

treeMap의 함수 중 lastKey() 와 firstKey()가 있다.

lastKey()는 map에서 가장 큰 key 값을,

firstKey()는 map에서 가장 작은 key 값을 알려주는 함수이다.

 

그렇기에 num이 1이라면 lastKey()를 사용해서 최대 키값을,

num이 -1이라면 firstKey()로 최소 키값을 구한다.

그리고 그 값을 n에 대입한다.

 

if(map.put(n, map.get(n)-1)==1) {
    map.remove(n);
}

다음으로, map에서 n의 value 값이 1이라면 map에서 제거하고,

그렇지 않다면 value 값을 1 감소시킨다.

 

 

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

3. 마지막으로 map의 사이즈가 0이라면 EMPTY를 출력하고,

그렇지 않다면 lastKey() 함수를 사용해 map의 최대 키값을, firstKey() 함수를 사용해 map의 최소 키값을 출력한다.

 

 

풀이 - PriorityQueue 2개 사용

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());

int T = Integer.parseInt(st.nextToken());
for(int t=0; t<T; t++) {
    int Q = Integer.parseInt(bf.readLine());
    StringBuilder sb = new StringBuilder();
    Queue<Integer> min = new PriorityQueue<Integer>();
    Queue<Integer> max = new PriorityQueue<Integer>(Collections.reverseOrder());
    Map<Integer,Integer> map = new HashMap<Integer, Integer>();

    for(int q=0; q<Q; q++) {
        st = new StringTokenizer(bf.readLine());
        String sign = st.nextToken();

1. 문제에서 주어진 입력을 받을 코드를 작성한다.

queue를 2개 생성한다.

min은 오름차순 정렬, max는 내림차순 정렬을 한다.

default는 오름차순 정렬이기 때문에 max 에 Collections.reverseOrder()를 해서 내림차순 정렬로 만들어준다.

그리고 map도 생성한다.

 

if(sign.equals("I")) {
    int num = Integer.parseInt(st.nextToken());
    min.add(num);
    max.add(num);
    map.put(num, map.getOrDefault(num, 0) + 1);
}else {
    int type = Integer.parseInt(st.nextToken());

    if(map.size() == 0) continue;
    if(type == -1) {
        delete(min, map);
    }else {
        delete(max, map);
    }
}

2. treeMap에서와 마찬가지로 I일 때, D 일 때로 조건을 나눈다.

I라면, min과 max 큐, 그리고 map에도 넣는다.

D라면, treeMap에서와 마찬가지로 map의 size가 0이라면 continue한다.

size가 0이 아니라면 다음 조건을 실행한다.

type이 -1이라면 delete 함수를 실행한다. 이때 인자로 min과 map를 전달한다. (-1일때는 최소값을 삭제하는거니까 !!)

type이 1이라면 max, map을 인자로 전달한다. (1일 때는 최댓값을 삭제하는거니까 !!)

 

public static int delete(Queue<Integer> queue, Map<Integer, Integer> map) {
    int num;
    while(true) {
        num = queue.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;
}

3. delete 함수를 실행한다.

매개변수로 들어온 queue가 min이라면 최솟값을 뺄 것이고, max라면 최댓값을 뺄 것이다.

이를 num에 담고, map에서 이 num의 value값을 cnt 변수에 담는다.

 

만약 cnt가 0이라면, continue한다.

cnt가 1이라면 map에서 제거하고,

cnt가 2 이상이라면 value 값을 1 감소시킨다.

그리고 while문을 탈출한 뒤 num을 return한다.

return 값은 2번에서는 필요 없고, 출력할 때 필요하다.

 

if(map.size() == 0) {
    sb.append("EMPTY");
}else {
    int res = delete(max, map);
    sb.append(res).append(" ");

    if(map.size() != 0) {
        res = delete(min, map);
    }
    sb.append(res);
}
System.out.println(sb);

4. 마지막으로 map의 사이즈가 0이라면 EMPTY를 출력한다.

map의 사이즈가 0이 아니라면 max 큐에서 최댓값을, min 큐에서 최솟값을 구해야한다.

 

출력할 때 최댓값, 최솟값 순서대로 출력하기 때문에 일단 최댓값 먼저 구한 뒤 res에 대입한다.

 

그 다음으로 최솟값을 구할 때는 map의 사이즈가 0이 아닌지 체크하는 조건이 필요하다.

 

왜냐하면 만약 map에 5 라는 숫자만 있다고 가정해보자.

이 5 는 최댓값이면서 최솟값이다. delete(max, map)에서 5를 이미 제거해버렸기 때문에,

map에는 어떤 수도 존재하지 않는다.

그렇기 때문에 만약 map의 사이즈가 0이라면 위에서 저장해뒀던 res를 재사용하고,

map의 사이즈가 0이 아니라면 delete(min, map)을 통해 최솟값을 구한다.

 

그리고 StringBuilder에 담긴 값을 출력한다.

 

 

 

코드 - TreeMap 2개 사용

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 bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		for(int t=0; t<T; t++) {
			TreeMap<Integer, Integer> map = new TreeMap<>();
			int Q = Integer.parseInt(bf.readLine());
			for(int q=0; q<Q; q++) {
				st = new StringTokenizer(bf.readLine());
				String input = st.nextToken();
				int num =Integer.parseInt(st.nextToken());
				
				if(input.equals("I")) {
					map.put(num, map.getOrDefault(num, 0) + 1);
				}else {
					if(map.size() == 0) continue;
					
					int n;
					if(num == 1) {
						n = map.lastKey();
					}else {
						n = map.firstKey();
					}
					if(map.put(n, map.get(n)-1)==1) {
						map.remove(n);
					}
				}
				
			}
			if(map.size() == 0) {
				System.out.println("EMPTY");
			}else {
				System.out.println(map.lastKey() + " " + map.firstKey());
			}
		}
	}
}

 

코드 - PriorityQueue 2개 사용

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		for(int t=0; t<T; t++) {
			int Q = Integer.parseInt(bf.readLine());
			StringBuilder sb = new StringBuilder();
			Queue<Integer> min = new PriorityQueue<Integer>();
			Queue<Integer> max = new PriorityQueue<Integer>(Collections.reverseOrder());
			Map<Integer,Integer> map = new HashMap<Integer, Integer>();
			
			for(int q=0; q<Q; q++) {
				st = new StringTokenizer(bf.readLine());
				String sign = st.nextToken();
				
				if(sign.equals("I")) {
					int num = Integer.parseInt(st.nextToken());
					min.add(num);
					max.add(num);
					map.put(num, map.getOrDefault(num, 0) + 1);
				}else {
					int type = Integer.parseInt(st.nextToken());
					
					if(map.size() == 0) continue;
					if(type == -1) {
						delete(min, map);
					}else {
						delete(max, map);
					}
				}
			}
			
			if(map.size() == 0) {
				sb.append("EMPTY");
			}else {
				int res = delete(max, map);
				sb.append(res).append(" ");
				
				if(map.size() != 0) {
					res = delete(min, map);
				}
				sb.append(res);
			}
			System.out.println(sb);
		}
	}
	public static int delete(Queue<Integer> queue, Map<Integer, Integer> map) {
		int num;
		while(true) {
			num = queue.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;
	}
}

 

TreeMap을 사용했을 때, 메모리와 시간이 더 적게 든 것으로 보인다.

 

 

참고한 블로그

(감사합니다 !!)

https://loosie.tistory.com/314

[BOJ] 백준 7662번 이중 우선순위 큐 (Java)

 

 

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