[프로그래머스] 더 맵게(Java, Level.2)

문제

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

 

입출력 예

 

풀이

1차 시도

스코빌 지수가 가장 낮은 2개 음식이라고 했으니, PriorityQueue에 저장하여 오름차순으로 정렬

오름차순 정렬한 후, 첫번째 원소를 가져와 K보다 크면 이미 모든 스코빌 지수가 K보다 크니까 그냥 0 반환

 

그렇지 않을 경우에는 while문에서 문제에 주어진 내용 계산 진행

먼저 answer ++ 이후 스코빌 지수 계산하여 다시 PriorityQueue에 넣어서 K보다 크도록 만들어주기!!

그 다음 PriorityQueue에서 가장 작은 원소가 K 이상이면 answer값 반환

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> scovileQueue = new PriorityQueue<>();
        for(int s : scoville) {
            scovileQueue.add(s);
        }
        
        if(scovileQueue.peek() >= K) return answer;
        while(true) {
            answer++;
            
            int min1 = scovileQueue.poll();
            int min2 = scovileQueue.poll();
            scovileQueue.add(min1 + (min2*2));
            
            if(scovileQueue.peek() >= K) {
                break;
            }
        }
        return answer;
    }
}

 

하지만 실패...

 

2차 시도

질문하기를 보니까 스코빌 지수를 K 이상으로 만들 수 없는 경우를 놓친 것 같음...!

while문 들어가기 전에 큐 크기가 1이하면 -1 반환!

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> scovileQueue = new PriorityQueue<>();
        for(int s : scoville) {
            scovileQueue.add(s);
        }
        
        if(scovileQueue.peek() >= K) return 0;
        if(scovileQueue.size() <= 1) return -1;
        while(true) {
            answer++;
            int min1 = scovileQueue.poll();
            int min2 = scovileQueue.poll();
            scovileQueue.add(min1 + (min2*2));
            
            if(scovileQueue.peek() >= K) {
                break;
            }
        }
        return answer;
    }
}

하지만 실패...

 

3차 시도

뭐가 문제이지... 하다가 다 돌았는데도 스코빌 지수가 K 미만인 경우를 제외한 것으로 판단

그래서 이번엔 while문 조건을 큐의 가장 작은 원소가 K  미만일 경우에만 수행

또한, 큐 크기가 1 이하일때에 -1 반환

계산을 계속 하다가 원소가 1개 남으면 계산를 못하고 더 이상 K 이상이 될 확률이 없으니까....!

 

최종코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> scovileQueue = new PriorityQueue<>();
        for(int s : scoville) {
            scovileQueue.add(s);
        }
        
        if(scovileQueue.peek() >= K) return 0;
        while(scovileQueue.peek() < K) {
            if(scovileQueue.size() <= 1) return -1;
            answer++;
            int min1 = scovileQueue.poll();
            int min2 = scovileQueue.poll();
            scovileQueue.add(min1 + (min2*2));
        }
        return answer;
    }
}

 

 

 

프로그래머스 문제

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

프로그래머스