[프로그래머스 / 더 맵게 / Java]

련지·2024년 8월 8일

42626 프로그래머스

코딩 테스트

목록 보기

4/9

...오랜만에 올리는 알고리즘 포스팅
누가 볼라나 싶었지만 할인 행사 포스팅의 조회수가 높은 걸 어제 발견 ㄴㅇㄱ
누군가에게 도움이 되길 바라며 써용...

오늘의 1솔 ♬

오늘의 문제는 프로그래머스의 Lv.2 더 맵게 !
바로 풀고 싶다면 요기로 → 문제 바로가기

문제 설명

레오는 매운 것을 좋아한다

모든 음식의 스코빌 지수가 K 이상이길 원한다

그러기 위해 가장 안 매운 두 음식을 섞어 비빔공식에 따라 스코빌 지수를 높인다

모든 음식이 스코빌 지수 K 이상인 상황이 되려면 음식을 최소 몇 번 섞어야 하는지 구하라(불가능하다면 -1을 반환하라)

풀이

스코빌 지수가 가장 낮은 두 음식을 계속 체크해야 한다
값의 최소값 or 최대값을 계속 꺼내 써야 한다면, Heap을 활용하는 것이 좋다

우선순위 큐

Java에서 Heap은 우선순위 큐(Priority Queue)로 사용 가능하다
기본적으로는 오름차순 정렬이 되기 때문에, 최소값을 뽑을 수 있는 최소힙으로 사용할 수 있다

최대값을 뽑는 최대힙으로 쓰고 싶다면, 아래처럼 정렬 순서를 바꿔줄 수 있다

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

참고로 이렇게도 쓸 수 있긴 한데...

PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2)->{o2-o1});

숫자 범위가 너무 크면 Integer 범위를 초과하는 경우가 생겨서 원하는 결과가 안 나올 수도 있다
그러니까 그냥 위의 방법을 쓰자!

접근 방법

=ㅅ= 암튼
풀이 과정은 아래와 같다

모든 음식의 스코빌 지수를 우선순위 큐에 넣는다

스코빌 지수의 최소값이 K 미만이라면 아래 과정을 반복한다

우선순위 큐의 사이즈가 1이라면 불가능한 경우이므로 -1을 반환한다
우선순위 큐의 사이즈가 1이다 == 음식의 종류가 하나밖에 없다
다 섞어 만든 음식 하나의 스코빌 지수가 K 미만이라면 더이상 가능한 방법은 없다

단계(answer)를 하나 증가시킨다

스코빌 지수가 가장 낮은 음식 두 개를 뽑는다

비빔공식에 따라 섞은 음식의 스코빌 지수를 구하고, 다시 우선순위 큐에 넣는다

코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int S = scoville.length;
        for(int s=0; s<S; s++){ pq.offer(scoville[s]); }
        while(pq.peek() < K){
            if(pq.size() == 1){ return -1; }
            answer++;
            int firstScoville = pq.poll();
            int secondScoville = pq.poll();
            int newScoville = firstScoville + 2 * secondScoville;
            pq.offer(newScoville);
        }
        return answer;
    }
}