99클럽 코테 스터디 9일차 TIL + 오늘의 학습 키워드

오늘의 학습내용

• 우선순위 큐

공부한 내용

우선순위 큐는 일반적인 FIFO 알고리즘을 가지고 있는 큐와 달리 삽입된 순서와 상관없이 값의 우선순위에 따라 추가되는 자료구조이다. 기본적으로는 낮은 숫자를 우선순위로 큐의 구조가 만들어진다. 일반적으로 힙 자료구조를 따른다.
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
반면 높은 숫자를 우선순위로 큐의 구조를 만드려면 comparator를 이용해야 한다.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b) -> b-a);

오늘의 회고

문제를 가장 먼저 보고 든 생각은 스코빌 지수가 낮은 순서대로 계속해서 쌓으려면 우선순위 큐 자료구조를 이용하자는 것이었다.

문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

내 풀이

가장 먼저 입력받은 파라미터를 우선순위 큐에 저장해놓고 가장 맵지 않은 음식이 스코빌 지수 K보다 작을때까지 일정한 반복문을 돌게끔 구현했다.
그 반복문 안에서는 큐의 크기가 2보다 크거나 같으면 가장 맵지 않은 음식과 그 다음으로 맵지 않은 음식을 꺼내 새로운 매운 음식을 만들고 다시 큐에 집어넣는다. 만약 큐의 원소가 하나이면 새로운 매운 음식이 생성되기 어렵기 때문에 이 경우엔 -1을 반환하게끔 구현했다.

package 프로그래머스;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 더_맵게 {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] scoville = new int[6];
        for(int i=0; i<6; i++){
            scoville[i] = Integer.parseInt(st.nextToken());
        }
        int K = Integer.parseInt(br.readLine());
        System.out.print(solution(scoville, K));
    }
    public static int solution(int[] scoville, int K){
        int answer = 0;
        int max = 1000000;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i=0; i<scoville.length; i++){
            queue.add(scoville[i]);
        }

        while(queue.peek() < K){ //가장 맵지 않은 음식이 K보다 작을때까지
            if(queue.size() >= 2){
                int most = queue.poll();
                int then = queue.poll();
                int newOne = most + then*2;
                answer ++;
                queue.add(newOne);
            }else{
                return -1;
            }
        }

        return answer;
    }
}

다른 사람 풀이

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> q = new PriorityQueue<>();

        for(int i = 0; i < scoville.length; i++)
            q.add(scoville[i]);

        int count = 0;
        while(q.size() > 1 && q.peek() < K){
            int weakHot = q.poll();
            int secondWeakHot = q.poll();

            int mixHot = weakHot + (secondWeakHot * 2);
            q.add(mixHot);
            count++;
        }

        if(q.size() <= 1 && q.peek() < K)
            count = -1;

        return count;
    }
}

처음에는 우선순위 큐로 구현하는게 맞을까? 고민했었는데 다른 사람의 풀이를 보고 그 댓글들을 확인해보니 우선순위로 구현하지 않을 경우 성능 평가에서 에러가 난다고 한다!