[백준] no7662: 이중 우선순위 큐

문제

: 최대값 최소값 출력 (비어있을 시, EMPTY출력)

 

T: 테스트 케이스 수

Q: 연산 수

I 숫자 : 숫자를 대기열에 입력 (중복입력 가능)

D + 1 : 대기열 중 최대값 제거 (중복시 하나만 제거)

D - 1 : 대기열 중 최소값 제거 (중복시 하나만 제거)

 

문제 링크 : https://www.acmicpc.net/problem/7662

---

원리

1. T만큼 테스트 케이스를 반복한다.

2. Q만큼의 연산을 반복한다.

3. 들어오는 값의 연산자가 I면 HashMap에 입력된 숫자를 key값으로 하고 value에는 1을 넣는다.

    이때 만약 이미 해당 key값이 존재하면, value에 +1 해준다. 

4. 들어오는 값이 D이고 숫자가 1이면, HashMap에서 Collections를 이용해 Max값을 구한다.

    이때 만약 Max값의 value가 1이 아니면 value에서 -1한다.

    만약 value가 1이면, 해당 key값을 통채로 지워버린다.

5. 들어오는 값이 D이고 숫자가 1이면, HashMap에서 Collections를 이용해 Min값을 구한다.

    이때 만약 Min값의 value가 1이 아니면 value에서 -1한다.

    만약 value가 1이면, 해당 key값을 통채로 지워버린다.

6. 만약 D가 들어오나, HashMap이 비어있으면, 별다른 작업 없이 통과한다.

7. 최종적으로 HashMap에 남은 숫자중 최대값과 최소값을 순차적으로 출력한다.

8. 만약 비어있으면 EMPTY를 출력한다.

 

---

풀이방법

1. HashMap 사용방법

: 문제를 해결 할 수는 있으나, 처리해야할 연산이 많아 오래걸림

* 메모리 332764kB, 시간 9616ms라는 경외로운 수치가 나왔다...ㅎ

 

2. Deque 사용 방법

: 얼핏보면 Deque나 Set으로 해결할 수 있을거 같지만, 중복인자를 허용한다는 점에 함정이 존재함

만약, 중복된 값을 제거할 때, 하나만 제거해야 하기 때문에 HashMap을 사용해서 value값을 -1하거나, 1일경우 해당 값을 제거한다. 

 

---

나의 코드

1. HashMap 사용방법

: 필자의 경우, static으로 둔 Map을 각 테스트 케이스마다 초기화(while문에서 초기화)를 안해서 백준에서 오답처리가 되었었다. 따라서, 각 테스트 케이스별로 대기열을 초기화시켜주는 것을 잊지말자

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

public class no7662 {

    private static Map<Integer, Integer> hm;

    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());
        int Q;
        StringTokenizer st;
        while(T-->0) {
            Q = Integer.parseInt(br.readLine());
            hm = new HashMap<>();
            for (int i = 0; i < Q; i++) {
                st = new StringTokenizer(br.readLine());
                operation(st.nextToken(), Integer.valueOf(st.nextToken()), hm);
            }

            if (hm.isEmpty()) bw.write("EMPTY\n");
            else {
                int max = Collections.max(hm.keySet());
                int min = Collections.min(hm.keySet());
                bw.write(""+max+" "+min+"\n");
            }
        }

        bw.close();
    }

    private static void operation(String op, Integer val, Map<Integer, Integer> hm) {
        if(op.equals("I")) {
            if(hm.containsKey(val)) hm.put(val, hm.get(val)+1);
            else hm.put(val, 1);
        } else if(op.equals("D") && val.equals(1)) {
            if(hm.isEmpty());
            else {
                int max = Collections.max(hm.keySet());
                if(hm.get(max)>1) hm.put(max, hm.get(max)-1);
                else hm.remove(max);
            }
        } else {
            if(hm.isEmpty()) ;
            else {
                int min = Collections.min(hm.keySet());
                if(hm.get(min)>1) hm.put(min, hm.get(min)-1);
                else hm.remove(min);
            }
        }
    }
}

 

2. Deque 사용 방법- [오답]

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

public class no7662 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Deque<Integer> dq;

        int T = Integer.parseInt(br.readLine());
        int Q;
        StringTokenizer st;
        while(T-->0) {
            Q = Integer.parseInt(br.readLine());
            dq = new ArrayDeque<>();
            for (int i = 0; i < Q; i++) {
                st = new StringTokenizer(br.readLine());
                operation(st.nextToken(), Integer.valueOf(st.nextToken()), dq);
            }

            if (dq.isEmpty()) bw.write("EMPTY\n");
            else {
                int max = dq.stream().mapToInt(a->a).max().getAsInt();
                int min = dq.stream().mapToInt(a->a).min().getAsInt();
                bw.write(""+max+" "+min+"\n");
            }
        }

        bw.close();
    }

    private static void operation(String op, Integer val, Deque<Integer> dq) {
        if(op.equals("I")) {
            dq.add(val);
        } else if(op.equals("D") && val.equals(1)) {
            if(dq.isEmpty());
            else dq.remove(dq.stream().mapToInt(a->a).max().getAsInt());
        } else {
            if(dq.isEmpty()) ;
            else dq.remove(dq.stream().mapToInt(a->a).min().getAsInt());
        }
    }
}