프로그래머스 더 맵게 JAVA

코딩테스트 연습 - 더 맵게

문제

해당 문제는 음식별 스코빌 지수가 주어졌을 때 K보다 작은 음식을 K이상의 스코빌 지수로 바꾸는 횟수를 구하는 문제다.

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

위와 같은 방법으로 모든 스코빌 지수가 K 이상이 되도록 반복해야 한다.

조건

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

풀이

해당 문제는 우선순위 큐를 사용하여 해결했다. 우선순위 큐의 경우 람다식을 이용해 정렬해주었고 (원래 오름차순이 기본인 거 같기도?) 처음 큐에 스코빌지수를 모두 넣고 이후 반복문을 통해 젤 작은 값을 빼내서 비교를 한 뒤 작을 경우 다음 값도 빼와서 연산을 진행하여 큐에 넣어주고 크거나 같으면 반복문을 빠져나온다. 만약 지금 큐에 값이 하나만 있고 그 값이 K보다 작다면 불가능하므로 -1을 리턴하고 종료한다.

코드

import java.util.PriorityQueue;

class Solution {
    public static int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> a - b); // 우선순위큐를 사용 람다식이용 오름차순 정렬
        for (int i = 0; i < scoville.length; i++) {
			pq.add(scoville[i]); // 스코빌 지수를 우선순위큐에 담는다.
		}
        while(true && !pq.isEmpty()) { // 무한루프
        	int a = pq.poll(); // 젤작은 값을 뺸다
        	if(a < K) { // 값을 비교한다
        		answer++; // 연산 횟수 증가
        		int b = pq.poll();
        		pq.add(a+b*2); // 연산해서 다시 우선순위큐에 넣는다
        	}else // K값보다 같거나 크면 반복문 빠져나옴
        		break;
        	if(pq.size() == 1 && pq.peek() < K) { // 만약 지금 큐에 값이 하나만있고 그 값이 K보다 작으면 불가능 -1 리턴
        		return -1;
        	}
        }
        return answer;
    }
}

https://github.com/JUNGSOONIL/JAVA/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20%EB%8D%94%20%EB%A7%B5%EA%B2%8C

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드