[G4] 이중 우선순위 큐 : Java : 7662

문제

7662번: 이중 우선순위 큐

---

 

 

 

 

접근 방법

맨 앞에는 항상 최솟값을, 맨 뒤는 항상 최댓값을 넣어서 유지 시키면 풀 수 있을 것이라 생각.

그래서 값을 삽입할 때마다 정렬된 순서로 넣어주는 것이 중요하다고 생각 했다.

 

방법1. 덱 쓰기

앞과 뒤를 넣고 뺴는 것이기 때문에 적합한 자료구조가 덱이라고 생각했다.

하지만 이제 정렬된 순서로 어떻게 넣어줄지를 구현해 보니깐 중간에 넣어줄 수 있는 방법이 없다는 것을 깨달았다!!!

 

방법2. Linked List 쓰기

삽입할 때 정렬된 순서로 넣어주기 위해 맨 뒤부터 비교해서 작은 값이 나타나면 그 위치에 넣어주는 방법으로 구현해봤다. 

하지만 시간초과!!! 이 방법이 아니였다. 삽입 되는 값이 최솟값에 가까울 수록 연산이 많아지며, 최악의 경우 O(n^2)이 된다.

 

방법3. 모두가 다 값을 넣어보는 것이 아닌가? 결과 중심으로 계산을 해보자

모두 시간 초과가 나니깐 방법을 달리 생각해서 모든 연산을 다 수행 하는 것이 아닌 결과 중심으로 해야되는가 고민했다.

그래서 먼저 삽입 연산 횟수, 제거 연사 횟수를 각 구해주고 리스트가 텅 비어서 연산이 무효화 되는 횟수를 구해보기도 해봤지만...

이 문제는 삽입과 제거의 관계가 중요하기 때문에 횟수만을 구해서는 의미 없었다.

 

방법4. TreeSet

결국 포기를하고 인터넷을 찾아봤다. 값을 넣기만 해도 자동으로 정렬을 해주는 자료 구조가 무엇인지. 인터넷에는 TreeMap을 쓰라고 했다. 하지만 이 문제는 값만 넣으면 되기에 TreeSet을 써봤다. 하지만 문제는 중복값을 넣을 수 없었다!!

그래서 중복값을 허용할 수 있도록 Comparator를 오버라이딩 해서 TreeMap을 생성할 때 인자로 넘겨줬다. 이때 문제는 1. 중복 값은 여전히 들어가지 않는다. 2. remove가 안된다 였다. 

 

찾아보니 중복값을 넣을 수 없는 문제는 TreeMap은 애초에 이진 검색 트리를 기반으로 한 Set이여서 애초에 불가한 것이다. TreeMap, NavigableSet, NavigableMap 또한 이진 검색 트리를 기반으로 한다.  중복된 값을 넣는 경우에 관리가 불편해지고 모호해져 정렬 유지와 효율성 측면의 이유로 제외 한다고 한다.

내가 오버라이딩 한 Compare함수는 정렬할 때 호출되는 함수로 정렬 순서를 정의하는데 사용하고 애초에 불가능한 것을 되게 만들지는 않는 것 같다.

 

 public static void main(String [] args) throws IOException {
 	 TreeSet<Integer> set = new TreeSet<>(new AllowedDuplecate());
 }


class AllowedDuplecate implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        if(o1 > o2) return 1;
        else if(o1 < o2) return -1;
        else return 0;
    }

}

 

 

방법 5. TreeMap

결국 중복 값을 저장하기 위해서 key에는 숫자 값을, value에는 횟수를 저장하여 구현하였다.

 

---

 

 

 

코드

import java.io.*;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class k_yujin {
    public static void main(String [] args) throws IOException {
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for(int t=0; t <T; t++){
            // 연산 횟수
            int n = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
            for(int i=0; i<n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String operator = st.nextToken();
                int value = Integer.parseInt(st.nextToken());

                // 삽입
                if(operator.equals("I")){
                    if(map.containsKey(value)){
                        map.replace(value, map.get(value)+1);
                    }
                    else{
                        map.put(value, 1);
                    }

                }

                // 제거
                else if(operator.equals("D")){
                    if(map.isEmpty()) {
                        continue;
                    }
                    if(value == -1){
                        int firstKey = map.firstKey();
                        if(map.get(firstKey) == 1){
                            map.remove(firstKey);
                        }
                        else{
                            map.replace(firstKey, map.get(firstKey)-1);
                        }
                    }
                    else if(value == 1){
                        int lastKey = map.lastKey();
                        if(map.get(lastKey) == 1){
                            map.remove(lastKey);
                        }
                        else{
                            map.replace(lastKey, map.get(lastKey)-1);
                        }
                    }
                }

            }
            if(map.isEmpty()){
                bw.write("EMPTY\n");
            }else{
                bw.write(map.lastKey()+" "+ map.firstKey()+"\n");
            }
        }
        bw.flush();
        bw.close();
    }
}