프로그래머스 [더 맵게]

[더 맵게] 문제설명

 

[더 맵게] 제한 사항

 

문제를 읽으며 풀이과정을 아래와 같이 그려보았다.

[더 맵게] 풀이 과정

조건1의 No return 0;은 처음부터 조합할 필요가 없는 scoville배열이 주어진 경우를 표현한 것이다.

조건 3의 yes return -1;은 k미만인 음식이 존재하지 않을 때까지 조합하다가 이제 더이상 조합할 음식이 없어졌을 경우(음식이 1개인 경우) 그 음식마저 k미만이라면 제한사항 4번째처럼 -1를 return 해준다는 것이다.

 

이를 코드로 구현해보면,

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int result = 0;
        boolean flag = false;
        //조건 1. K 미만인 음식이 존재하는가?
        for(int i=0;i<scoville.length;i++){
            if(scoville[i]<K) flag=true;
        }

        //조건1 -> 존재하면 우선순위 큐에 추가, 아니라면 return 0;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        
        if(flag){
            for(int i:scoville){
                priorityQueue.offer(i);
            }
        }else return 0;

        //조건2. 음식이 1개인가?(조합하다보면 발생하기에)
        while(priorityQueue.size()>=2){
            //조합한다
            priorityQueue.offer(priorityQueue.poll()+(priorityQueue.poll()*2));
            result++;
            //조건2-1. 여전히 k 미만인 음식이 존재할 경우 loop 조건검사 반복, 아닐경우 return result(조합횟수)
            if(priorityQueue.peek()>=K){
                return result;
            }
        }
        
        //조건3. 음식이 한 개인 경우, 그 음식의 스코빌이 K미만인가?
        if(priorityQueue.size()==1 && priorityQueue.poll()<K) result = -1;
        
        return result;
    }
}

 

[더 맵게] 실행 결과