[코딩테스트 연습] 더 맵게

- 문제

[문제링크]
매운 것을 좋아하는 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 합니다.

• 입출력 예
  

-전체코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        List<Integer> scovList = new ArrayList<>();
        scovList = Arrays.stream(scoville).boxed().collect(Collectors.toList());
        PriorityQueue<Integer> scovQueue = new PriorityQueue<>(scovList);
        // stream사용하지 않고 for문
        // for(int i : scoville) {
        //     scovQueue.add(i);
        // }
        
        while(scovQueue.peek() < K) {
            if(scovQueue.size() < 2) {
                answer = -1;
                break;
            }
            else {
                scovQueue.add(scovQueue.poll()+scovQueue.poll()*2);
                answer++;
            }
        }
        
        return answer;
    }
}

- 막혔던 점 & 해결방법

주어진 scoville배열을 List로 만들어 이를 계속 정렬하면서 최소값이 K이상이 될 때까지 반복하게 만들었습니다. 정확성 테스트는 통과하였으나, 효율성에서 시간 초과로 실패하였습니다. 매반복마다 정렬하는 것이 시간을 크게 소요한다고 생각되어 List가 아니라 TreeSet을 사용하려고 했으나 이는 중복값을 허용하지 않는 문제가 있었습니다. 이 문제를 해결하기 위해 찾던 중 우선순위큐를 찾게 되었고 이를 적용하여 쉽게 해결하였습니다. [참고글][참고글2]

- 느낀점

이전에 풀었던 오픈채팅방 문제와 마찬가지로 적절한 자료구조를 선택하는 것이 문제의 핵심이라고 생각됩니다. 자료구조 수업에서 이번 문제에서 사용한 우선순위큐를 포함해 다양한 자료구조를 배웠지만 사용해본 경험이 적거나 없는 자료구조는 쉽게 떠오르지 않았습니다.