[2주차 - 3] 이중 우선순위 큐

문제

문제 사이트: 백준
문제 이름: 이중 우선순위 큐
문제 번호: 7662

문제 풀이 템플릿

### 시간복잡도 생각해보기
- 

### 풀이 아이디어
- 

### 의사코드 / 풀이 과정
-

시간복잡도 생각해보기

T의 범위는 없고, k는 1,000,000이 최댓값 이므로, 최대 시간 복잡도는 O(NlogN) 이다.

풀이 아이디어

TreeMap을 이용하여 값을 key에 저장하고, 키가 중복되는 수는 value에 카운트한다.
최솟값을 지울 땐 TreeMap.firstKey() 를 이용하여 값을 찾아 value - 1 또는 값을 지운다.
최댓값을 지울 땐 TreeMap.lastKey() 를 사용하여 값을 찾아 value - 1 또는 값을 지운다.

의사코드 / 풀이 과정

int T ← input()
for(1 to T) {
  tree ← TreeMap
  int k ← input()
  for(1 to k) {
    String op ← input()
    int number ← input()
    if(op = "I") {
      tree.put(number, number.getOrDefault(number, 0) + 1)
    } else if(op = "D") {
      if(tree.isEmpty()) {
        continue
      }
      if(number = 1) {
        int key ← tree.lastKey()
      } else {
        int key ← tree.firstKey()
      }
      if(tree.get(key) > 1) {
        tree.put(key, tree.get(key) - 1)
      } else {
        tree.remove(key);
      }
    }
  }
  print(result) // 적절한 답 출력
}

시간복잡도 생각해보기

k ≤ 1,000,000
최대 시간 복잡도는 O(KlogK)에서 정리되어야 함
TreeMap에서 주요 연산 시간 복잡도는 최대 O(KlogK)
테스트 케이스 T개에 대해 최종 시간 복잡도 : O(T*KlogK)

풀이 아이디어

중복값이 가능함을 고려해, 특정 숫자가 입력된 빈도수를 저장할 구조가 필요
우선순위에 따라 최댓값, 최솟값을 제거하는 연산 필요 -> 매번 하는 정렬로는 시간복잡도 초과 예상
<숫자,빈도수>를 저장할 수 있고 오름 차순 정렬 가능한 TreeMap 사용

의사코드 / 풀이 과정

TreeMap<Integer, Integer> map : <숫자, 빈도수> 구조로 저장하는 map

매 테스트 케이스마다 반복

입력받은 k번 만큼 반복

if(커맨드 == "I"){
    map.put(숫자, map.getOrDefault(숫자,0)+1));
} else { // "D" 입력
    map이 비어있으면 continue;

    int val = 숫자 == 1 ? map.lastKey() : map.firstKey();
    if(map에서 val의 빈도수를 -1 했을 때 결과가 1인 경우){ // 모두 제거됨 의미
          map.remove(val);
    }
}

시간복잡도 생각해보기

k ≤ 1,000,000 → 10^6이므로 O(N logN)으로 진행

유형	우선순위 큐 (PriorityQueue)	트리맵 (TreeMap)
삽입	O(log N)	O(log N)
조회	O(1) (최상위 요소)	O(log N)
삭제	O(log N)	O(log N)

풀이 아이디어

원소의 개수를 카운트할 Map을 사용
우선순위를 보장하는 자료구조들을 이용하여 구현
- PriorityQueue 2개(오름차순 ,내림차순) + HashMap
- TreeMap
PriorityQueue 2개를 사용하는 경우
- 원소의 개수를 파악하기 위해 HashMap을 이용
- 계속 각각의 peek가 HashMap에 존재하는지 체크해줘야 함.. 번거로움
TreeMap을 사용하는 경우
- 추가적인 연산 필요 없이 TreeMap에서 원소의 개수를 파악하고 최댓값, 최솟값 반환 가능

위: 트리맵 / 아래: 우선순위 큐

의사코드 / 풀이 과정

트리맵 기준으로 적습니다..😸


def main()
...
TreeMap<Integer, Integer> tm // value는 해당 key 원소의 개수
while (q-- > 0)
// 명령어에 따라 분기 처리
if (`I`일 경우) 
tm.put(number, tm.getOrDefault(number, 0) + 1);
if (`D`일 경우 && !tm.isEmpty())
int key // 
if (최댓값 반환일 경우)
  key = tm.lastKey(); // 트리맵의 최댓값 반환
if(최솟값 반환일 경우)
  key = tm.firstKey(); // 트리맵의 최솟값 반환

// 원소의 개수 줄이고, 0개가 되면 트리맵에서 삭제
tm.put(key, tm.get(key) - 1);
if (tm.get(key) == 0)
  tm.remove(key);

// 출력 if(tm.isEmpty()) // "EMPTY" else // 조건에 맞게 출력



> -2^31이상 2^31미만인 정수라서 오버플로우남... 함정 😿

시간복잡도 생각해보기

k의 범위가 k ≤ 1,000,000 이므로 O(NlogN) 내로 해결해야 한다.

풀이 아이디어

TreeMap으로 선언을 해준다.

의사코드 / 풀이 과정

int t <- input()
for (int i = 0 -> t - 1) {
    TreeMap<Integer, Integer> tm = new TreeMap<>()
    int n <- input()
    for (int j = 0 -> n - 1) {
        String f <- input()
        if (f == "I") {
            tm.put(num, tm.getOrDefault(num, 0) + 1)
        } else if (f == "D") {
            if (!tm.isEmpty() && num == 1) {
                int removeNum = tm.lastKey()
                if (tm.get(removeNum) == 1) tm.remove(removeNum)
                else tm.put(removeNum, tm.get(removeNum) - 1)
            }
            if (!tm.isEmpty() && num == -1) {
                int removeNum = tm.firstKey()
                if (tm.get(removeNum) == 1) tm.remove(removeNum)
                else tm.put(removeNum, tm.get(removeNum) - 1)
            }
        }
    }
}
if (tm.isEmpty()) 
    print("EMPTY\n")
} else {
    print(tm.lastKey() + " " + tm.firstKey() + "\n")
}

틀린코드

1. 첫 번째

우선순위큐 문제라 PriorityQueue 2개를 각각 오름차순, 내림차순으로 선언해서 해줬는데 시간초과가 났다. 두 개의 PriorityQueue에 remove 연산을 해서 시간이 오래 걸리는 것 같다. $\rightarrow$ TreeMap으로 해결했다.

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> ascendPq = new PriorityQueue<>();
        PriorityQueue<Integer> descendPq = new PriorityQueue<>(Collections.reverseOrder());
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            for (int j = 0; j < n; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String f = st.nextToken();
                if (f.equals("I")) {
                    int num = Integer.parseInt(st.nextToken());
                    ascendPq.add(num);
                    descendPq.add(num);
                } else if (f.equals("D")) {
                    int num = Integer.parseInt(st.nextToken());
                    if (!descendPq.isEmpty() &&  num == 1) {
                        int remove = descendPq.remove();
                        ascendPq.remove(remove);
                    }
                    if (!ascendPq.isEmpty() && num == -1) {
                        int remove = ascendPq.remove();
                        descendPq.remove(remove);
                    }
                }   
            }
            if (ascendPq.isEmpty() || descendPq.isEmpty()) {
                System.out.println("EMPTY");
            } else {
                System.out.println(descendPq.peek() + " " + ascendPq.peek());
            }
        }
    }
}

2. 두 번째

$\rightarrow$ 내림차순으로 선언할 때, @Override를 하는 방식으로 변경

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            TreeMap<Integer, Integer> tm = new TreeMap<>((o1, o2) -> o1 - o2); // 여기서 오류 발생, 중복 값을 허용하므로 에러나는 것으로 추정
            int n = Integer.parseInt(br.readLine());
            for (int j = 0; j < n; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String f = st.nextToken();
                if (f.equals("I")) {
                    int num = Integer.parseInt(st.nextToken());
                    tm.put(num, tm.getOrDefault(num, 0) + 1);
                } else if (f.equals("D")) {
                    int num = Integer.parseInt(st.nextToken());
                    if (!tm.isEmpty() && num == 1) {
                        int remove = tm.lastKey();
                        if (tm.get(remove) == 1) tm.remove(remove);
                        else tm.put(remove, tm.get(remove) - 1);
                    }
                    if (!tm.isEmpty() && num == -1) {
                        int remove = tm.firstKey();
                        if (tm.get(remove) == 1) tm.remove(remove);
                        else tm.put(remove, tm.get(remove) - 1);
                    }
                }
            }
            if (tm.isEmpty()) {
                System.out.println("EMPTY");
            } else {
                System.out.println(tm.lastKey() + " " + tm.firstKey());
            }
        }
    }
}

시간복잡도 생각해보기

-최대로 10의 6승이므로 O(NlogN) 까지만 가능함.

TreeMap 사용: O(logN)
TreeMap은 레드블랙 트리 기반으로 균형이 잡혀있어서 삽입, 삭제, 검색 모두 O(logN)이다.
삽입시 자동으로 정렬이 이뤄지고, 별도의 정렬 연산이 필요하지 않다.
풀이 아이디어
TreeMap을 이용해서 Key 는 입력받은 num, Value는 갯수를 세준다. 중복 가능하기 때문에 Value를 꼭 정해줘야 함.

lastKey, firstKey를 이용해서 최대와 최소를 빼주고, 만약 삭제한 후의 Value값이 0이되면 아예 map에서 제거해준다 (핵심)

틀린 코드/ 아이디어


public class Main {
static int T;
static int K;
static PriorityQueue<Integer> pq; //오름차순 
static PriorityQueue<Integer> dpq; //내림차순 
static HashMap<Integer,Boolean> map;
public static void main(String [] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    T = Integer.parseInt(br.readLine());
    for(int test = 0; test< T ; test++) {
        K = Integer.parseInt(br.readLine());
        pq = new PriorityQueue<>();
        dpq = new PriorityQueue<>(Collections.reverseOrder());
        map = new HashMap<>();
        for(int i = 0; i<K;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String m = st.nextToken();
            int num = Integer.parseInt(st.nextToken());
            if(m.equals("I")) {
                pq.offer(num);
                dpq.offer(num);
                map.put(num, true);
            }else if(m.equals("D") && num == -1 &&!pq.isEmpty() && !dpq.isEmpty()){ //최솟값삭제
                int min = pq.peek();
                if(!map.get(min)) {
                    pq.remove();
                }
                if(!pq.isEmpty()) {
                    map.put(min, false);
                    pq.remove();
                }
            }else if(m.equals("D") && num == 1 && !pq.isEmpty() && !dpq.isEmpty()) { // 최댓값삭제
                int max = dpq.peek();
                if(!map.get(max)) {
                    dpq.remove();
                }
                if(!dpq.isEmpty()) {
                    map.put(max, false);
                    dpq.remove();
                }
            }
        }
        if(pq.isEmpty() || dpq.isEmpty()) {
            sb.append("EMPTY").append("\n");
        }else {
            sb.append(dpq.peek()).append(" ").append(pq.peek()).append("\n");   
        }
    }
    System.out.println(sb);     
}
}

- deque 사용해야하나  -> 우선순위 queue 구현하기 어려워보임
- 우선순위 큐 두개 -> 두개 큐의 원소가 달라서 삽입 삭제가 자주 일어날경우 키가 꼬임 
- 그래서 우선순위 큐에서 hashMap을 사용해서 boolean 값으로 표현하려고 했는데, 생각해보니깐 중복이 가능하니 map.remove() 한후에 할걸 생각도 든다...
- 다시 풀어보려고 했는데 큐 동기화가 빡세서 안할거다 
### 의사코드 / 풀이 과정
```java
for(int i = 0; i<K;i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        String m = st.nextToken();
        int num = Integer.parseInt(st.nextToken());
        if(m.equals("I")) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }else if(map.size() == 0){
            continue;
        }
        else if(m.equals("D") && num == -1){ //최솟값삭제
            remove(map.firstKey());
        }else if(m.equals("D") && num == 1) { // 최댓값삭제
            remove(map.lastKey());
        }
    }
    if(map.size()==0) {
        sb.append("EMPTY").append("\n");
    }else {
        int min = map.firstKey();
        int max = map.lastKey();
        sb.append(max).append(" ").append(min).append("\n");    
    }
}

T4F1 / Algorithm

[2주차 - 3] 이중 우선순위 큐 #19

문제

문제 풀이 템플릿

시간복잡도 생각해보기

풀이 아이디어

의사코드 / 풀이 과정

시간복잡도 생각해보기

풀이 아이디어

의사코드 / 풀이 과정

시간복잡도 생각해보기

풀이 아이디어

의사코드 / 풀이 과정

시간복잡도 생각해보기

풀이 아이디어

의사코드 / 풀이 과정

틀린코드

1. 첫 번째

2. 두 번째

시간복잡도 생각해보기

풀이 아이디어

틀린 코드/ 아이디어