[프로그래머스/42626] 더 맵게

23 Jan 2025 in Study / Coding Test

• ☑️ 문제
• ☑️ 풀이
  • 실패한 풀이
  • 성공한 풀이

☑️ 문제

프로그래머스 42626

☑️ 풀이

실패한 풀이

• PriorityQueue 를 써서 가장 작은 스코빌 지수와 두 번째로 작은 스코빌 지수를 poll() 메서드를 이용해서 뽑는다.
• PriorityQueue 의 맨 앞의 지수가 가장 작은 스코빌 지수이고, 이 지수가 7이라면 모든 지수가 7이상이라는 것이기 때문에 while 문의 조건을 queue.peek() ≤ K 로 설정하였다.
• 테케를 반은 통과하고 반은 실패했다.
  • 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다. 라는 제한 사항을 놓쳤기 때문이다.
  • 이 경우는 어떻게 체크해야 할까?

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0; i < scoville.length; i++) {
            queue.offer(scoville[i]);
        }
        
        while (queue.peek() < K) {
            int first = queue.poll();
            int second = queue.poll();
            queue.add(first + (second * 2));
            answer++;
        }

        return answer;
    }
}

성공한 풀이

• while 문의 종료 조건에 queue.size() > 1 을 추가해줬다.
• while 문이 종료되면 해당 PriorityQueue 에는 지수가 1개 남는 것이며, 이 지수가 7이 안되면 K 이상 만들 수 있는 지수가 없는 것이기 때문에 -1 를 리턴해준다.

//시간: 2.47ms
//메모리: 91.8MB

import java.util.*;

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

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0; i < scoville.length; i++) {
            queue.offer(scoville[i]);
        }

        while (queue.size() > 1 && queue.peek() < K) {
            int first = queue.poll();
            int second = queue.poll();
            queue.offer(first + (second * 2));
            answer++;
        }

        if (queue.peek() < K) {
            answer = -1;
        }

        return answer;
    }
}