더 맵게

이리·2024년 10월 17일

프로그래머스

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42626

문제설명

모든 음식 스코빌 지수를 K이상으로 만들고싶다.
스코빌 지수를 높이기위해 가장 낮은 두 음식을 섞어 새로운 음식을 만든다.
섞은 음식 S = 가장 맵지 ❌ S + (두번째 맵지 ❌ S * 2)
주어진 파라미터: S 지수가 담긴 int[] scoville, 목표 S 지수 int K

풀이방법

정렬을 할 수 있어야한다.
가장 작은 수 두개를 섞는 함수를 별도로 마련한다.
정렬이 되어있으니 가장 작은수가 K보다 크면 OK
while문을 돌릴 생각인데 size()가 1개인데 K보다 작으면 -1를 출력하는 탈출 코드를 작성한다.

풀이

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int count = 0; // 섞는 횟수 
        List<Integer> SList = new ArrayList<>(); // ArrayList로 정렬 편리하게 조정
        
        // 리스트 옮기기
        for(int i : scoville){
            SList.add(i);
        }
        
        Collections.sort(SList);
        // 원소가 모두 K보다 커야한다. -> 가장 아래 요소 두개를 합쳐 다시 정렬하는 함수 필요 sorting 
        // 가장 작은 원소가 K보다 크면 된다.
        // 충족할수 없을 수 있으니 원소가 하나뿐인데 K보다 작으면 -1을 출력하는 코드 필요 
        while(SList.get(0) < K){
            
            // 탈출 조건 
            if(SList.size() == 1){
                count = -1;
            }
            
            // 섞기실행 
            mix(SList);
            count++;
        }
       
        return count;
    }
    
    // 섞는 함수 
    public List<Integer> mix(List<Integer> SList){
        //일단 정렬 
        Collections.sort(SList);
        
        // 가장 첫 작은 원소 두개 빼서 섞기
        int a = SList.get(0);
        int b = SList.get(1);
        //삭제(삭제하면 인덱스 변경되니 주의)
        SList.remove(1);
        SList.remove(0);
        
        int c = a + (b*2);
        SList.add(c);
        
        // 다시 정렬 
        Collections.sort(SList);
        
        return SList;
    }
}

⇒ 시간 초과났다. 그럴줄 알았다. 근데 해법은 몰랐다.

⇒ 서칭 했다.

⇒ Priority Queue 라는 놈이 있단다.

⇒ 서칭 했다.

Priority Queue란?

= 우선순위 큐

일반적인 큐는 FIFO 형식의 자료구조인데 우선순위 큐의 경우 들어가는 순서와는 상관없이 우선순위가 가장 높은 데이터가 먼저 나가는 자료구조이다. 우선순위 큐의 경우 힙 자료구조를 통해서 구현될 수 있다.

→ 그래서 우선 순위는 어떻게 정하는데??

Priority Queue 선언 방법

// 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>();
 
// 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());

기본적인 메서드

add() : 우선순위 큐에 원소를 추가. 큐가 꽉 찬 경우 에러 발생
offer() : 우선순위 큐에 원소를 추가. 값 추가 실패 시 false를 반환
poll() : 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 null 반환
remove() : 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 에러 발생
isEmpty() : 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 에러 발생
clear() : 우선순위 큐를 초기화
size() : 우선순위 큐에 포함되어 있는 원소의 수를 반환

Priority Queue를 적용해 보았다.

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        
        // 오름 차순으로 정렬하는 우선순위 큐 
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        // 섞는 횟수
        int count = 0; 
        
        // 옮기기 
        for(int i : scoville){
            pQ.add(i);
        }
        
        while(pQ.peek() < K){
            // 탈출 조건
            if(pQ.size() == 1 && pQ.poll() < K){
                count = -1;
                break;
            }
            
            // size가 1보다 클 경우 
            // n1, n2 섞기
            int n1 = pQ.poll();
            if(n1 < K){
                int n2 = pQ.poll();
                pQ.offer(n1 + (n2*2));
                count++;
            }else{
                break;
            }
        }
        return count;
    }
}