[프로그래머스] 더 맵게!!

1. 문제

---

 

문제 설명

매운 것을 좋아하는 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회입니다.

 

 

 

2. 아이디어

---

Priority Queue를 사용하자. 자바에서는 Min Heap을 사용한다.

The head of this queue is the least element with respect to the specified ordering.

Priority Queue에 대한 설명은아래 글을 참고.

간단히말해서 Min Heap의 경우 가장 작은 값을 맨 앞으로 가져옴. 단 그 뒤에 데이터는 정렬되어 있지는 않음.

단, Head는 가장 작은 것을 보장. Max Heap은 반대

 

따라서 가장 큰 값, 또는 가장 작은 값만 사용할 경우 Priority가 유용할 수 있음.

 

자료구조-비선형

 

평균 수행시간이 O(logN)인 알고리즘 : Heap 정렬 & element 삭제

 

평균 수행시간이 O(logN)인 알고리즘 : Heap 정렬 & element 추가

• 이 경우에는 가장 작은 두 개의 값이 필요하다.
• 스코빌 배열을 Priority Queue로 변환하고 섞을 두 스코빌 지수를 Queue에서 꺼낸다.
• data를 꺼낼 때 마다 정렬이 다시 이루어진다.
• 따라서 두 번 째 data를 꺼낼때에도 해당 Queue에서 가장 작은 값 꺼냄.
• 이후 공식에 의해 두 스코빌을 섞은 후 Queue에 추가한다.
• 이 때 해당 Queue에서 가장 작은 값이 Head로 가게됨.
• 이 때 head가 K보다 크거나, 또는 다 섞어서 스코빌이 1개 남았는데, K보다 작은 경우 종료된다.

 

3. 코드

---

public int solution(int[] scoville, int K) {
    int answer = 0;
    PriorityQueue<Integer> scovileQueue = new PriorityQueue<>();

    for (int s : scoville) {
        scovileQueue.add(s);
    }

    while (!scovileQueue.isEmpty()){
        answer++;
        int s1 = scovileQueue.remove();
        int s2= scovileQueue.remove();
        int s3 = s1 + (s2*2);
        scovileQueue.add(s3);

        if (scovileQueue.peek() >= K){
            break;
        }else if (scovileQueue.size()==1){
            return -1;
        }
    }

    return answer;
}

 

 

 

4. GitHub: 211129 Scoville

---

GitHub - bsh6463/coding_test