[백준] 알고리즘 분류(자료구조,JAVA)7662번, 이중 우선순위 큐

문제 링크

7662번: 이중 우선순위 큐

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 이중 우선순위 큐는 가장 큰 값과 가장 작은 값을 제거할 수 있습니다.

2. I는 값 저장, D는 값 제거를 뜻합니다.

3. 각 테스트마다 명령문을 진행한 후 최대값 및 최소값을 결과로 출력합니다.

4. 테스트가 끝날 때 큐가 비어있으면 "Empty"를 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 테스트마다 명령어을 진행합니다.

 

3. 각 테스트마다 큐에 저장된 값에 따른 결과를 출력합니다.

 

 

명령어 진행

 

오름차순 정렬되는 PriorityQueue : Up

내림차순 정렬되는 PriorityQueue : Down

현재 큐에 저장된 수의 개수를 저장하는 HashMap<Integer, Integer> : cnt

 

명령어 : I value

 

Up에 value 저장

Down에 value 저장

cnt에 value(key)에 값 + 1

 

 

명령어 : D 1

 

Down에서 순차대로 poll()하며 cnt를 통해 존재하면 제거!

cnt에 poll(key)에 값 - 1

 

명령어 : D -1

 

Up에서 순차대로 poll()하며 cnt를 통해 존재하면 제거!

cnt에 poll(key)에 값 - 1

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

※테스트케이스가 2개지만 1번째 테스트케이스만 진행되는 과정을 보여드리겠습니다.

 

T : 2

N : 7

 

명령어

 

I : 6

I : -5643

D : -1

D : 1

D : 1

I : 123

D : -1

 

2. 각 테스트마다 명령어을 진행합니다.

 

I : 6(6 저장)

 

Up : 6

Down : 6

cnt : (6, 1)

 

I : -5643(-5643 저장)

 

Up : -5643, 6

Down :  6, -5643

cnt : (6, 1), (-5643, 1)

 

D : -1(최소값 빼기)

 

Up : 6

Down : 6, -5643

cnt : (6, 1)

 

D : 1(최대값 빼기)

 

Up : 6

Down : -5643

cnt : 

 

D : 1(최대값 빼기)

※큐가 비어있습니다.

 

Up : 6

Down : -5643

cnt : 

 

I : 123(123저장)

Up : 6, 123

Down : 123, -5643

cnt : (123, 1)

 

D : -1(최소값 빼기)

Up :  -5643

Down : 6, 123

cnt : 

 

 

3. 각 테스트마다 큐에 저장된 값에 따른 결과를 출력합니다.

 

cnt에 아무것도 없기 때문에 큐는 비어있습니다.

 

EMPTY을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 명령문을 띄어쓰기 기준 나누었습니다.
• 각 테스트마다 poll함수를 이용하여 'D'와 'I'에 대한 명령어를 진행합니다.
• 각 테스트마다 종료될 때 큐가 비어있으면 "EMPTY", 값이 있으면 getNum을 통해 최대값과 최소값을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• poll함수는 cnt와 우선순위큐를 이용해서 최대값이나 최소값을 제거합니다.
• getNum함수는 cnt와 우선순위큐를 이용해서 최대값이나 최소값을 구합니다. 

 

결과코드

 

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

class Main {

    public static void main(String args[]) throws IOException{
        //입력값 처리하는 BufferdReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //각 테스트케이스 진행
        for(int test_case=0;test_case < T;test_case++){
            PriorityQueue<Integer> up = new PriorityQueue<>();	//오름차순 Up
            //내림차순 Down
            PriorityQueue<Integer> down = new PriorityQueue<>(Comparator.reverseOrder());
            HashMap<Integer, Integer> cnt = new HashMap<>();	//cnt
            int N = Integer.parseInt(br.readLine());
            int size = 0;	//큐에 저장된 개수
            //명령어 진행
            for(int i=0;i<N;i++){
                st = new StringTokenizer(br.readLine()," ");
                //명령어 저장
                char command = st.nextToken().charAt(0);
                int value = Integer.parseInt(st.nextToken());
                if(command == 'I'){		//'I' 진행
                    //큐에 저장
                    up.add(value);
                    down.add(value);
                    //cnt + 1
                    cnt.put(value, cnt.getOrDefault(value, 0) + 1);
                    size++;	//큐 개수 증가!
                }else {
                    //'D' 진행
                    if (size <= 0)	//현재 큐가 비어있으면 넘기기
                        continue;
                    size--;		//큐 개수 감소
                    if (value == -1) {	//최소값 제거
                        poll(up, cnt);
                    } else		//최대값 제거
                        poll(down, cnt);
                }
            }
            //큐가 비어있을 때
            if(size <= 0)
                bw.write("EMPTY\n");
            else{	//최대값, 최소값 BufferedWriter 저장
                bw.write( getNum(down, cnt)+ " " + getNum(up, cnt) + "\n");
            }
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //'D' 명령어로 최소값이나 최대값 제거 진행하는 함수
    static void poll(PriorityQueue<Integer> pq, HashMap<Integer, Integer> cnt){
        //큐에 존재하는 최대값이나 최소값 탐색
        while(!pq.isEmpty()){
            int temp = pq.poll();
            if(cnt.get(temp) == 0)	//큐에 존재하지 않는 수일 때
                continue;
            cnt.put(temp, cnt.get(temp) - 1);	//최대값이나 최소값 제거!
            break;
        }
    }
    //최대값이나 최소값 구하는 함수
    static int getNum(PriorityQueue<Integer> pq, HashMap<Integer, Integer> cnt){
        //큐에 존재하는 값 탐색
        while(!pq.isEmpty()){
            int temp = pq.poll();
            if(cnt.get(temp) == 0)	//큐에 존재하지 않는 값일 때
                continue;
            return temp;	//최대값이나 최소값 반환
        }
        return -1;
    }
}