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

7662번: 이중 우선순위 큐

 

이 문제도 엄청 틀린 문제이다

---

 - 문제설명

첫번째 줄은 테스트케이스의 수, 두번째 줄 입력은 첫번째 테스트 케이스의 입력 데이터 수

각각의 테스트 데이터는 "문자  숫자"의 형태로 이루어져있다

문자가 들어오면 해당 문자가 I인지 D인지 확인하고 I이면 input, D이면 delete를 수행한다

D문자가 들어오면 숫자가 -1이면 최소값을 빼주고 1이면 최대값을 빼준다

 

 

 - 실패와 원인

처음에는 두개의 우선순위 큐를 사용하여 (최댓값 정렬하는 maxQ, 최소값 정렬하는 minQ)

각각의 큐에 데이터를 저장하고 빼주는 형식으로 구현했는데 

delete -1이 들어오면 최소값큐에 poll 하고 해당 값을 최대값큐에도 빼줘야한다.

하지만 이 과정인 remove(obejct)는 큐의 처음부터 해당 obejct가 있는지 확인하며

수행하기  때문에 당연히 시간초과가 난다.

(remove(object) 의 시간복잡도 O(N) 근데 이게 for문안에 들어있다?)

그래서 Map을 사용하여 삭제하려는 index를 가지고 해당 index만 삭제하도록 구현하였다.

 

 

 - 구현 방법

처음에는 Node를 사용하여 index와 값을 저장하려 했지만 결국 실패하고...

블로그를 찾아보던 중

map.getOrDefault(n,0)

을 사용하여 구현하는 방법을 참고하여 구현하였다.

Map에 저장할 때 key값을 입력한 숫자로 저장하고, map.getOrDefault를 통해 갯수를 저장하였다.

getOrDefault : 찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 메서드

 

만약 해당 메서드를 통해 찾는 키가 없다면 0 +1을 저장한다.

만약 찾는 키가 있다면 해당 값에 +1한 값을 저장한다.

자세한 설명은 아래 코드 주석에 있다

 

---

 - 코드와 주석

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class B7662 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < T; i++) {
            PriorityQueue<Integer> minQ = new PriorityQueue<>();
            PriorityQueue<Integer> maxQ = new PriorityQueue<>(Comparator.reverseOrder());
            Map<Integer, Integer> map = new HashMap<>();

            int k = Integer.parseInt(br.readLine());

            for (int j = 0; j < k; j++) {
                st = new StringTokenizer(br.readLine()," ");
                String s = st.nextToken();
                int n = Integer.parseInt(st.nextToken());

                if(Objects.equals(s, "I")){
                    minQ.add(n);
                    maxQ.add(n);
                    // Map을 사용하여 저장하는 값을 key 값으로 두고
                    // 해당 값이 없으면 default 값인 0에 1을더하여 1을 저장한다
                    // 만약 있으면 해당 갯수에 +1
                    map.put(n, map.getOrDefault(n,0) +1 );
                }else{
                    if(map.size()==0) continue;
                    if(n==-1){
                        delete(minQ,map);
                    }else{
                        delete(maxQ,map);
                    }
                }
            }


            if(map.size()==0){
                sb.append("EMPTY").append('\n');
            }else{
                // 최대값 최소값 출력
                // 최소 최대값이 같으면 (최대값 poll후 size가 0이면) 최대값을 두번 출력한다
                int res = delete(maxQ, map);
                sb.append(res).append(" ");
                if(map.size()>0) res = delete(minQ, map);
                sb.append(res).append('\n');
            }
        }
        System.out.println(sb);
    }

    private static int delete(PriorityQueue<Integer> queue, Map<Integer, Integer> map) {
        int num;
        while(true){
            num = queue.poll();
            // maxQ나 minQ에서 꺼낸 값이 map에 있는지 확인하고
            // 없으면 계속 반복한다
            int cnt = map.getOrDefault(num,0);
            if(cnt == 0) continue;
            // 해당 값이 1이면 제거 (해당값이 하나만 있으면)
            if(cnt == 1)
                map.remove(num);
            else
                //해당 값이 여러개면 한개 줄여서 저장
                map.put(num, cnt-1);
            break;
        }
        return num;
    }
}