더 맵게

문제 링크는 아래와 같습니다.

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

최근에 유튜브에서 재밌으면서 유익한 영상을 보게 되었습니다.

https://youtu.be/PFKPdjdWbQ8

원래도 입력 값의 범위가 중요하다고 생각했으나,

이 영상을 본 기점으로 더더더 입력 값의 범위를 꼼꼼하게 체크하게 되었다ㅋㅋ

처음 문제를 봤을 때는 느낀점은 '입력 값이 너무 큰데..?!'였다.

절대로 이중 반복문을 사용하면 안된다고 생각했다. 

그러면서 고민한 부분이 있었다. '그러면 정렬은 어떻게 해야하지..?'

그래서 자바에서 우선순위 큐에 대한 자료구조를 찾아보게 되었고,

PriorityQueue 자료구조가 우선순위 큐와 같이 동작한다는 것을 배웠다.

 

그래서 PriorityQueue를 사용해 문제를 손쉽게 해결할 수 있었다.

아래는 PriorityQueue의 짧은 사용예시다.

//값이 낮은 것이 우선 순위가 높다.
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//값이 높은 것이 우선 순위가 높다.
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

 

역시 문제 해결을 위한 자료 구조 선택이 중요하다는 것을 다시금 깨달았으며, 많은 것을 배운 문제였다.

정답 코드는 아래와 같다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        for (int i : scoville) {
            queue.add(i);
        }

        while(true){
            if(queue.peek() < K){
                int min = queue.poll();
                if(queue.peek() == null){
                    answer = -1;
                    break;
                }
                int nextMin = queue.poll();
                queue.add(min + (nextMin * 2));
                answer++;
            }
            else break;
        }
        return answer;
    }
}

 

이상으로 포스팅을 마칩니다. 감사합니다.