프로그래머스 더 맵게

프로그래머스 더 맵게 문제

문제는 프로그래머스에서 출제된 더 맵게 문제이다.

문제상황

• 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

• Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
  Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

풀이

• 첫 번째로 생각 했었던건 Queue이다. Queue에 scovill의 배열 값을 저장하고 반복문을 돌리면서 scovill의 지수값을 Queue에 삽입하면서 반복문의 조건으로 K값보다 작을 때까지 반복문을 돌리는 생각을 하였다. 그 반복문을 돌리는 과정중에는 정렬을 해야하기 때문에 sort() 메서드를 호출했다. 결과론적으론 테스트도 실패가 있었고 효율성 테스트에서도 실패였다...흐규
  • 다시 코드를 생각해 보았다. sort()라는 메서드가 처리값이 많을 거 같아서 어떻게 하면 Queue에서 정렬을 따로 하지 않고 Queue안에 값들이 정렬 될 수 있을까??? 정답은 우선순위 큐였다...(오우 쮓) Queue에 넣으면 자동적으로 우선순위를 정하면서 값들이 정렬이 된다.
  • 그 다음으로 조건으로 Queue.peek() < K와 또 하나의 조건이 필요하였다. Queue안에 사이즈가 1보다 클 때였다. Queue.size() > 1
  • 그리고 또 하나!!!! 내가 간과한게 있었다.. 이것때메.. ㅠㅠ 조금 시간이 걸렸다... 문제에도 있었는데 ㅠㅠㅠ 마지막으로 Queue.peek()의 값이 무조건 적으로 K보다 클 때가 아닐 수도 있다는 걸 ....간과하였다. 그래서 Queue.peek() < K return -1;

---

최종코드

public class Solution2 {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pQueue = new PriorityQueue<>();
        int count = 0;

        //우선순위 큐에 scoville 데이터 저장하기
        for (int i=0; i<scoville.length; i++) {
            pQueue.add(scoville[i]);
        }

        while (pQueue.peek() < K && pQueue.size() > 1) {
            pQueue.offer(pQueue.poll() + (pQueue.poll() * 2));
            count++;
        }
        if (pQueue.peek() < K) return -1;
        return count;
    }

}