프로그래머스 : 더 맵게(Java)

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

코딩테스트 연습 - 더 맵게

 

[문제]

 

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

[입출력 예]

 

 

---

[풀이]

 

 처음에는 ArrayList로 풀어보려 했는데 테스트 케이스에서 계속 막히는 부분이 생겼다. 그래서 다른 분들의 풀이를 찾아 봤는데 대부분이 우선순위 큐로 푼 것을 알게 됐다. 먼저, scoville 배열에 있는 값을 우선순위 큐에 담았다. 이후, 스코빌 지수를 확인하며 값 2개를 추출 및 계산한 값을 다시 넣는 과정을 반복하면 된다. 우선순위 큐에 대해서 익숙하지 않았기에 이 기회에 공부를 하게 되었다. 따로 글을 작성할 것까지는 아닌 것 같고 요약을 해보자!

 

[우선순위 큐 (Priority Queue)]

 

 일반적으로 큐가 FIFO의 구조를 가졌다면 우선순위 큐는 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다. 일반적으로 힙을 이용하여 구현하며 데이터를 추가할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성한다. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있으므로 시간 복잡도는 O(NLogN)이다.

 

<Priority Queue 구현>

 

- 선언

// Integer타입의 우선순위 큐 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

// Integer타입의 우선순위 큐 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

- 추가

priorityQueue.add(값);     // 우선순위 큐 값 추가
priorityQueue.offer(값);   // 우선순위 큐 값 추가

- 삭제 및 값 반환

priorityQueue.poll();       // 우선순위 큐에 첫번째 값을 반환 및 제거 만약 비어있다면 null값 반환
priorityQueue.remove();     // 우선순위 큐 첫번째 값 제거
priorityQueue.clear();      // 우선순위 큐 초기화

 

---

[코드]

 

import java.util.PriorityQueue;

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

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

        while (priorityQueue.peek() <= K) {
            if (priorityQueue.size() == 1) {
                return -1;
            } else {
                int a = priorityQueue.poll();
                int b = priorityQueue.poll();

                int value = a + 2 * b;

                priorityQueue.offer(value);
                answer++;
            }
        }
        return answer;
    }
}