99클럽 코테 스터디 9일차 TIL , 더 맵게

문제

풀이

모든 음식을 원하는 스코빌지수에 맞추고 싶은 성격 이상한 Leo가 있다.

가진 음식의 스코빌 지수를 담은 배열이 주어지면 모든 음식이 원하는 스코빌 지수 이상이 되도록 해줘야 한다.

스코빌 지수를 맞추는 방법은 가장 작은 스코빌 지수 + (두 번째로 작은 스코빌 지수 * 2)를 반복하여 모든 음식의 스코빌 지수를 맞춰준다. 예를 들어 위의 예시와 같이 입력이 주어진다면

[1,2,3,9,10,12] , 7 이 주어진다면

1. 1 + (2 * 2) = 5 -> [5,3,9,10,12]

2. 3 + (5 * 2) = [13,9,10,12]

두번이면 원하는 스코빌지수 이상이 됐으므로 2를 return 한다.

 

풀이 1 - 제출 못함

예시는 스코빌 지수가 오름차순으로 입력됐지만 꼭 그러리라는 조건은 없다.

해서 Arrays.sort로 오름차순 정렬 후 ArrayDeque를 만들어서 앞에서부터 계산해 가며 코드를 작성하려고 했다.

보통 풀이를 시작 후 풀어가면서 모호함이 해결되는 경우가 많았는데, 코드를 작성하면서도 모호함이 해결되지 않았다.

 

풀이 2 - 배낌 ㅜ

결국 남의 풀이를 확인했다.

heap 자료구조를 알고 있어야 하는 문제였다.

사실 stack 이나 queue 자료구조는 문제 풀이에서 자주 나와서 접해보고 공부했었는데 heap은 거의 사용해 본 적도 공부해 본 적도 없다. 비전공자라서라고 핑계를 대기에는 공부할 시간은 많았다. 하여튼 heap에 대한 공부내용은 후술 한다.

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;

        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for(int x : scoville) heap.add(x);

        while(heap.size() > 1 && heap.peek() < K){
            int first = heap.poll();
            int second = heap.poll();

            heap.add(first + (second * 2));
            answer++;
        }
        
        if(heap.peek() < K) answer = -1;
        
        return answer;
    }
}

 

heap자료구조에 대해 알고 우선순위 큐를 사용했더니 너무나 쉽게 깔끔하게 풀렸다.

poll을 두번 해줘야 하기에 size 조건과 가장 작은 값이 K보다 작은지 조건을 걸고 음식을 섞어준다.

heap에 남은 마지막 값이 K보다 작으면 -1을 출력한다.

 

TIL

Heap 자료구조에 대해 알아보자(java..)

 

• heap 자료구조에 대해 공부했다.
• 자료구조를 잘 알고 있으면 문제풀이가 훨씬 쉬워진다.