더 맵게

코딩테스트 연습 - 더 맵게 | 프로그래머스 (programmers.co.kr) 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
• 주어진 자료는 무엇인가?
• 조건은 무엇인가?
• 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
• 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라.

- 모든 음식의 스코빌 지수를 K 이상으로 만드는 것이 목표

- 스코빌 지수가 가장 낮은 두 개의 음식을 규칙에 따라 섞는다. 

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

- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 리턴함 

2. 계획

• 전에 비슷한 문제를 알고 있는가?
• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
• 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
• 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
• 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
• 자료는 모두 사용했는가?
• 조건을 모두 사용했는가?
• 문제에 포함된 핵심적인 개념은 모두 고려했는가?

- 우선순위 큐를 사용하면, 음식들을 스코빌 지수가 낮은 순서대로 정렬할 수 있다.

- 모든 음식을 우선순위 큐에 담아 넣고, 2개씩 빼면서 섞은 음식의 스코빌 지수를 계산한다

- 섞은 음식은 다시 우선순위 큐에 넣는다. 

- 가장 스코빌 지수가 낮은 음식의 스코빌 지수가 K이상인지 검사한다. 

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int i=0; i<scoville.length; i++){
            int num = scoville[i];
            pq.add(num);
        }
        
        while(true){
            if(pq.peek() >= K){
                break;
            }
            
            if(pq.size() == 1){
                answer = -1;
                break;
            }
            
            int num1 = pq.poll();
            int num2 = pq.poll();
            int newNum = num1+2*num2;
            pq.add(newNum);
            answer++;
        }
        
        return answer;
    }
}

4. 반성

• 문제를 다른 방식으로 해결할 수 있는가?
• 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
• 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
• 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?

- 문제를 처음 풀 때, 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 리턴한다는

  조건을 고려하지 않아서 런타임 에러가 발생했다.

-> 문제의 예외 조건들을 문제 이해 단계에서 주의 깊게 읽고 고려해야 한다. 

 

- 문제의 제한 사항에 scoville의 길이가 최대 100만이하라는 제한 사항이 있다.

-> 이는 정렬을 할 때, 이중 for문을 사용하면 안되고,

    PriorityQueue와 같이 시간 복잡도가 O(nlogn)인 자료구조를 사용하라는 의미가 숨어 있다.

-> 이 숨어 있는 의미에 대해 한 번 생각을 해봐야 한다.  

 

- PriorityQueue에서 값을 꺼내는 메소드는 poll()이다.

-> Queue, PriorityQueue에서 맨 앞의 값을 확인하는 메소드는 peek(), 

    값을 꺼내는 메소드는 poll()이라는 점을 기억해야 한다.