프로그래머스 레벨2 더 맵게 (JAVA)

오우쉣..

 

더 이상은 못풀줄 알았던 레벨2가 하다 보니 풀리게 되는데.. 신기하다

 

 

이번에 푼 문제는

 

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

코딩테스트 연습 - 더 맵게

 

더 맵게 이다

 

이 문제를 풀면서 Queue구조지만

 

우선순위가 존재해서 우선순위별로 정렬이 되는 Queue 구조인

 

Priority Queue에 대해 알게 되었다.

 

이 문제의 핵심은 

 

가장 작은 수 + 그다음으로 작은 수 * 2  를 하여  K를 만드는 거다 

 

배열에 있는 모든 수를 저 공식으로 K까지 만드는 횟수를 구하는 거다

 

Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

 

라는 조건 때문에 Priority Queue를 사용하면 문제를 쉽게 풀 수 있다.

 

모든 코드는 GitHub 에 올려놓았다.

 

 

코드는 이러하다..

 

import java.util.PriorityQueue;


class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (Integer integer : scoville) {
            queue.add(integer);
        }

        while (true) {
            if(queue.size() == 1 && queue.peek() < K) {
                return -1;
            }
            
            if (queue.peek() >= K) {
                return answer;
            }

            int n = queue.poll() + (queue.poll() * 2);
            queue.add(n);
            answer++;

        }
    }
}

queue의 size 가 1이고 그 값이 K보다 작다면 이건 만들 수 없다

return -1 해준다

 

Priority Queue는 정렬이 된다. 

그럼 가장 낮은 수부터 앞으로 가게 되고 Queue는 앞에서부터 값이 나온다

 

queue의 첫 번째 값이 K보다 크다면 그 뒤에 값은 전부 K보다 큰 값이다

 

그럼 answer 값을 return 시켜준다

 

저 조건에 안 맞는다면 공식을 진행해준다.

 

공식대로 만든 값을 queue에 다시 넣어주고 정렬이 됨으로써

 

다음 while에서는 가장 작은 값부터 공식을 진행할 수 있게 된다.

 

후기

 

이제 진짜.. 2레벨 더 풀 수 있는게 없는거 같은데..!