문제 출처

코딩테스트 연습 > 힙(Heap) > 더 맵게
https://school.programmers.co.kr/learn/courses/30/lessons/42626

문제 설명

스코빌 지수가 들어있는 배열 scoville, 스코빌 지수의 기준이 되는 K가 주어질 때,

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

mixFood = first + (second x 2)

해당 식대로 음식을 섞어 새로운 음식을 만든다.
모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복해서 섞는 경우 최소 횟수를 return 하라.

제한 사항

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

접근 방법

scoville 배열의 요소를 PriorityQueue에 삽입하고, 이를 주어진 식에 대입한다. 식을 통해 만들어진 값을 PriorityQueue에 삽입하고 answer의 값을 증가시킨다.

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++){
            pq.offer(scoville[i]);
        }
        
        
        while(pq.size() > 1 && pq.peek() < K){
            int first = pq.poll();
            int second = pq.poll();
            
            int mixFood = first + (second * 2);
            
            pq.offer(mixFood);
            answer++;
            
            if(pq.size() < 2 && pq.peek()<K){
                return -1;
            }
        }
        
        return answer;
    }
}

알게된 점

문제에 대한 접근은 어려운 편은 아니다. 하지만, 제한 사항을 함께 고려하면 생각할 것이 조금은 생긴다.
가장 중요하다고 생각한 제한 사항은

모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

이다. 해당 부분은 반복문을 통해 실행하여 반복문을 더 이상 실행할 수 없는데(pq.size() <2) PriorityQueue 안에 요소 값이 K 이상이 될 수 없을 때를 고려해야한다.

처음에 이 문제를 접했을 땐 List를 이용해서 풀려고 했지만 List Collections.sort()의 시간 복잡도가 O(nlogn)이기 때문에 최종 시간 복잡도가 O(n^2logn)이 나와 너무 커진다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        List<Integer> sc = new ArrayList<>();
        
        for(int n : scoville){
            sc.add(n);
        }
        Collections.sort(sc);
        
        while(!sc.contains(0) || sc.get(0) >= K){
            int mixFood = sc.get(0) + sc.get(1);
            sc.add(mixFood);
            Collections.sort(sc);
            answer++;
        }
        return answer;
    }
}

% 심지어 while문의 조건도 잘못 설정했다.

문제푼 흔적