[20201218] 프로그래머스 - 더맵게 (Queue, PriorityQueue, 가장 작은 수를 꺼내고 그다음 작은수 꺼내기)

문제 설명

매운 것을 좋아하는 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 합니다.

입출력 예

scoville                                                                                                     K              return

[1, 2, 3, 9, 10, 12]

7

2

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

 

[해결 방안]

음식을 섞는데 쓰인 원소는 배열에서 삭제되는 것(배열에서 빠짐)이 관건이라고 생각했다.

Queue를 사용해서 FIFO(선입선출) 방식을 이해해야 한다. 

그 중에서도 우선순위가 먼저인 요소가 먼저 빠져나가는 Priority Queue를 사용해야 한다.

레오가 원하는 스코빌지수 k보다 작은 값이 우선순위가 되어, 섞는 작업을 거친다.

그리고 음식이 1개면 섞을거 없으니깐 -1 리턴하면 된다.

 

[매냐의 풀이]

import java.util.*;
import java.util.stream.*;       // Collectors를 쓰기위함
import java.util.ArrayList.*;    // remove를 쓰기위함 
import java.util.LinkedList; 
import java.util.Queue; 

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        // 계산에 쓰인 숫자들은 사라진다
//         List<Integer> scoList = new ArrayList(Arrays.stream(scoville).boxed().collect(Collectors.toList())); 
        
//         for (int i=0; i<scoList.size(); i++) {
//             Collections.sort(scoList);  // 빼고넣고 하면 재정렬
//             // System.out.println(scoList); 
//             // System.out.println("이번에 사용할 인덱스" + scoList.get(i)); 

//             if (scoList.size() < 2) {
//                 return -1;
//             }
            
//             if (i < scoList.size()-1 && scoList.get(i) < K) {
//                 int mix = scoList.get(i) + (scoList.get(i+1) * 2);
//                 scoList.remove(i); // 가장 작은거 삭제
//                 scoList.remove(0); // 두번째 작은거 삭제
//                 // System.out.println("추가값:" + mix);  
//                 scoList.add(mix);
//                 i -= 1;
//                 answer += 1;    // mix값 생길때마다 섞은횟수 추가
//             } else if (i == scoList.size() && scoList.get(i) < K) {
//                 return -1;
//             }
            
//         }
              
        
        
        // Queue<Integer> pq = new LinkedList<>();    // 일반큐와 비교
        PriorityQueue<Integer> pq = new PriorityQueue<>();
		for (int i = 0; i < scoville.length; i++) {
			pq.add(scoville[i]);        // Array를 우선순위큐로 변환
		} 

		while (pq.peek() < K) {     // 가장작은수 꺼내서 비교, 맨앞으로 보냄
			if (pq.size() < 2) {    
				return -1;          // 음식 1개면 섞을 수 없으므로
			}

			int a = pq.poll();      // 가장작은수 꺼내서 없앰, 변수로 지정
			int b = pq.poll();      // 가장작은수 꺼내서 없앰, 변수로 지정
			pq.add(a + 2 * b);

			answer++;
            // System.out.println(pq);
		}

        return answer;
    }
}

 

[깨달은 것]

레오.. 그는 대체 왜 매운 음식을 즐기는가...

그래도 전공때 자료구조 수업 A+맞던 보람이 있는 문제였다(자랑)

많은 주석이 알려주듯 나의 오만가지 생각을 담은 코드이다.

지우면 깔끔하겠지만 나중에 봤을 때 '너가 이렇게 멍청했었어!' 라고 알려주고 싶어서 남겼다. 

사실은 Java에 Queue라는 객체가 있는 줄 몰랐다. 자료구조 시간에 이런거 왜 배우지 했는데, 오늘에서야 깨달았다.

 

특히 내가 생각하는 우선순위큐와 일반큐의 차이를 서술하자면,

일반큐는 원소를 add할 때 바로 맨 뒤에 넣는다.

우선순위큐는 add한 값을 일단 맨 뒤에 넣어보고, 부모보다 작으면 앞으로 한칸씩 보낸다.

어떠한 기준에 쎄게 부합하면 먼저 나가는 개념이다.

 

조금 바보같지만 이걸 정확히 이해하기위해서 일반큐와 우선순위큐로 바꿔보고 콘솔에 출력해가며 비교했다. 

 

[사용된 skill]

import java.util.LinkedList.*;    // 큐를 사용하기 위한 임포트

import java.util.Queue;

 

peek() : 가장 작은 수를 지정, 맨앞으로 보냄.

poll() : 가장 작은 수를 꺼내서 없앰. 변수로 지정 가능