[프로그래머스 : 레벨 2] 더 맵게 (feat. PriorityQueue , Java)

이번 문제는 내가 List로 문제를 풀고 나니 효율성에서 문제가 생겼다. 

그래서 이걸 어떻게 해결하지 해서 일단 문제가 Heap과 관련된 문제이기도 했고 

가장 작은수를 더 빠르게 구하는것이니 자바의 PrioritQueue라는 클래스를 사용하여서 문제를 풀었다.

 

PriorityQueue를 사용하는 방법은 아래 링크에 올려놨다.

https://wpioneer.tistory.com/95

 

 

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다.

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을

아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

 

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 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 합니다.

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

 

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

문제 풀이

모든 배열의 수가 K이상이 되려면 몇번 섞어야 하는지 구하기

 

나의 소스

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        //스코빌 지수를 List에 담기
        PriorityQueue<Integer> sList = new PriorityQueue<>();
        
        for(int i : scoville){
            sList.offer(i);
        }
        
        for(int i = 0;i<sList.size();i++){
            if(sList.peek() < K && sList.size() != 1){ //맨앞에 있는게 K보다 작고 길이가 1이상
                answer++; //섞은 횟수 증가
                
                int first = sList.poll(); //제일 작은수 빼고
                int second = sList.poll(); //그다음으로 작은수 뺀다.
                int result = first + (second*2); //스코빌 공식
                sList.offer(result); //섞어서 집어넣기
                
                i = -1; //다시 처음부터 확인하게 하기
            }
        }
        if(sList.size() == 1 && sList.peek() < K){
            return -1;
        }
        
        return answer;
    }
}

 

일단 내가 제일 먼저한건 물론 PriorityQueue에 값을 넣은것이다.

 

그리고 그다음은 해당 큐에 접근하여서 일일히 값을 비교해본것이다.

위소스는 어려운게 딱히 없기에 주석만으로 설명을 마치겠다.

 

느낀점

1. 문제를 좀더 자세히 읽고 뭘 원하는지 제대로 알자.

2. 효율성에 문제가 있기전에 일단 생각나는대로 해봐라(시간절약은 위한)

3. 그리고 웬만해선 효율성있게 코딩을 하도록 하자.

4. 가장 큰수, 가장 작은수를 빠르게 가져오려면 Heap을 사용하자.