문제

[프로그래머스] 더 맵게
https://school.programmers.co.kr/learn/courses/30/lessons/42626

풀이

조건

• 모든 음식의 스코빌 지수를 K 이상으로 만든다.
• 섞은 음식의 스코빌 지수는 섞은 음식의 스코빌 지수 =
  가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

풀이 순서

• 우선순위 큐(pq)를 사용한다.
• 스코빌 지수가 가장 낮은 값(min)을 사용해 종료 조건을 비교한다.
• while문을 사용해 반복 횟수(answer)를 찾는다.
  • min이 K 이상이 되면 종료된다.
  • pq의 크기가 1 이하가 되면 종료된다.
  • pq에 남아있는 가장 작은 값이 K보다 작으면 -1을 출력한다.

코드

Java

public static int solution(int[] scoville, int K) {
        int answer = 0;
        
        // 우선순위 큐 사용
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        // 데이터 삽입
        for(int value : scoville) {
        	pq.add(value);
        }
        
        // 현재 가장 스코빌 지수가 낮은 값 찾기
        int min = pq.peek();
        // 연산 반복
        while(K > min && pq.size() > 1) {
        	int a = pq.poll();
        	int b = pq.poll();
        	
        	int nScale = a + b * 2;
        	
        	pq.add(nScale);
        	answer++;
        	min = pq.peek();
        }
        
        // 반복문 종료
        // -> pq에 값이 1개 이하 남음
        // -> 더 이상 조합할 수 없음
        // 그 하나 남은 값의 스코빌 지수가 K보다 작다면 -1 
        if (K > min) {
        	answer = -1;
        }
                    
        return answer;
    }

정리

• 우선순위 큐를 사용한다는 것은 알았지만 while 문을 처리하는 과정에서 오류가 있어 테스트케이스 1개가 통과하지 못해 시간이 좀 걸렸다.