[프로그래머스 Level 3] 이중우선순위큐 (Java 자바)

어제 치른 PCCP 시험에서 바보같은 실수를 했다 .... 점수제로 이루어지는 PCCP 시험에서 10초 남은 시간임에도 다른 코드 고치다가 return 을 미리 구현해두지 않아 문제 다 풀어놓고 테스트 케이스를 돌려볼 수도 없게 해버렸다 .... ㅠㅠ 만점일 수도 있는걸 0점 만들어버린셈 😫 

 

지금 생각해보면 그 전날 늦게 자서 잠을 많이 못 잔 탓에 오전에 정신이 없었던 거 같다. 아쉽지만 이미 지나간건 어쩔 수 없는 일이고,, 앞으로 잘하면 된다 ㅎㅎ

 

주말에 하루에 1개씩 코테 시험 치르고 뼈저리게 느낀건 ,,, 다시 코테 감각 끌어올려야지 !! 퇴사하자마자 꿀 같은 방학에 제주 여행 갔다가 공부 깔짝하고 여수 여행 갔다가 바로 유럽으로 떠나버린 나 ,,,, 신나게 놀 거 다 놀았으니 이제 진짜 공부해야겠다 싶은데 확실히 거의 2달을 놓아버리니 까먹은 부분이 은근 있었다. 그래서 다잡은 생각으로는 오전에 하루에 1개씩 어려운 문제 접근해보기 !!

 

평소에 어려운 문제를 기피하는 경향이 있는데 그러다보니 실전에서도 굉장히 골치 아프게 느껴지고 두렵다. 이런 감정을 극복해야지 기업 코딩테스트 관문을 가볍게 뚫는 사람이 되리라 생각한다. 2023년 하반기 누구보다 열심히 보내보자 :)

 

 

 

프로그래머스 <이중우선순위> 문제 보기

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

 

 

프로그래머스 <이중우선순위큐> 문제 풀이

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

class Solution {
    
    static String[] operation;
    static String order;
    static int num, count, key;
    static TreeMap<Integer, Integer> map;
    
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        
        map = new TreeMap<>();
        
        for(int i=0; i<operations.length; i++){
            operation = operations[i].split(" ");
            order = operation[0];
            num = Integer.valueOf(operation[1]);
            
            if(order.equals("I")){
                map.put(num, map.getOrDefault(num, 0)+1);
            } else{
                if(map.size() == 0) continue;
                
                if(num == -1){
                    key = map.firstKey();
                } else{
                    key = map.lastKey();
                }
                
                count = map.get(key);
                if(count == 1){
                    map.remove(key);
                } else{
                    map.put(key, count-1);
                }
            }
        }
        
        if(map.size() != 0){
            answer[0] = map.lastKey();
            answer[1] = map.firstKey();
        }
        
        return answer;
    }
}

이중우선순위큐를 구현하는 문제였다. 백준에서 위와 거의 동일한 문제를 풀었던 경험이 있어서 알고리즘을 다시 떠올리기 좋았다. 일반적으로는 우선순위큐를 2가지 선언하여 나눠서 구현하는 방식을 떠올릴 수 있는데, java에서는 TreeMap을 사용하여 더욱 편하게 구현할 수 있다.

 

TreeMap은 가장 큰 특징들로는 정렬된 hash map 이라는 점, firstKey() 와 lastKey() 메소드를 통해 트리 내부의 최댓값 및 최솟값을 반환해준다는 점 등등이 있다. 아래에서 TreeMap만의 특징들 위주로 기능을 간단히 설명해보려 한다.

 

 

 

우선 알고 있어야 할 점은 TreeMap의 경우 (key, value) 형태로 저장할 수 있다. 아래와 같이 선언할 수 있다.

TreeMap<Integer, Integer> map = new TreeMap<>();

 

 

 

1. firstKey(), lastKey()

key = map.firstKey(); // 최솟값
key = map.lastKey(); // 최댓값

firstKey()의 경우 map에 있는 key들 중 최솟값을 반환한다.

lastKey()의 경우 map에 있는 key들 중 최댓값을 반환한다.

 

 

 

2. map.getOrDefault()

map.getOrDefault(n, 0);

map.put(n, map.getOrDefault(n, 0)+1);

map.getOrDefault(n, 0) 은 map에서 n을 key로 찾았을 때 존재한다면 해당 value를 반환, 존재하지 않는다면 0을 반환하게 한다. 즉, key가 존재하면 value 값을 반환, 아니라면 기본 값(해당 예제 0)을 반환하는 것이다.

 

TreeMap은 같은 key로 주입할 경우 똑같은 값이 또 추가되는 것이 아니라 덮어쓰는 경향이 있다. 따라서 두번째줄과 같이 value 값을 변환시켜 map에 해당 key가 몇번 입력되었는지 셀 수 있도록 할 수 있다. 위에서 설명했듯이 key가 존재하지 않으면 0을 반환하기에 +1된 1을 value로 하여 map 에 넣음으로써 해당 key가 한번 들어왔음을 알려준다. 반면 key가 이미 map에 존재할 경우 map.getOrDefault(n, 0)이 해당 key의 value값을 반환하기 때문에 value+1로 하여 map에 넣음으로써 해당 key의 개수를 하나 늘려준다.

 

 

 

3. map.get()

map.get(key)를 통해 해당 key의 value 값을 가져올 수 있다.

 

 

 

4. map.put()

map.put(key, value) 를 통해 map에 값을 추가할 수 있다.

 

 

 

5. map.remove()

map.remove(key)를 통해 해당 key와 value를 삭제할 수 있다.

 

 

 

 

개인적으로 map, set, comparable 등등 부분이 부족하다고 생각되어 9월에는 여기에 집중해볼까 싶다. 물론 다른 알고리즘도 같이 챙겨갈거지만!! 코딩테스트란 벽 때문에 면접까지 가지도 못하는건 너무 아쉬운 결과라고 생각된다. 하반기에는 아쉬운 결과 없도록 해야지 ㅎㅎ 그래도 파이썬에서 자바로 코테 바꾼다고 2달 전까지만 해도 자바 익히느라 Level1 다시 풀고 그랬는데 금방 Level 2~3까지 온 거 보면 좀 뿌듯하다. 조금 욕심이지만 Level4 까지도 풀어보고 싶다.