[Programmers] 더 맵게

[작성일]

• 2022-02-11

[분류]

• Set
  
  
  

[문제링크]

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

[요구사항]

• 모든 음식의 스코빌 지수가 K이상이 될 때까지 음식을 섞고 횟수를 출력해라.
  
  
  

[풀이]

우선순위 큐(최소 힙)을 이용해서 문제를 해결하였다. 가장 스코빌 지수가 작은 음식이 K이상이 되는 경우 모든 음식의 스코빌 지수가 K이상이 되는 점을 활용한다.

1) 최소 힙에 모든 음식을 넣는다.

2) 가장 작은 값을 확인하고 K보다 작은 경우 문제에서 주어진 공식에 따라 가장 작은 2개의 음식을 선택해서 새로운 스코빌 지수를 만들고 큐에 넣는 과정을 반복한다. 이 때, count++ 해준다.

3) 가장 작은 값이 K이상이 될 경우 누적된 count를 출력한다.

[코드]

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int sc : scoville) {
            pq.add(sc);
        }

        int cnt = 0;
        while(true) {
            if(pq.peek() >= K) return cnt;
            if(pq.size() <= 1) return -1;
            
            int a = pq.poll();
            int b = pq.poll();
            int nsc = a + 2*b;
            pq.add(nsc);
            cnt++;
        }
    }
}

[통과여부]

[느낀점]

일전에 풀었던 문제랑 거의 유사해서 쉽게 해결할 수 있었다.