(Lv2) 더 맵게

문제 설명

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

입출력 예

scovilleKreturn

[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회입니다.

---

내 접근 방법

1. 먼저 배열의 각각의 수가 > K 하게 만들어줘야 한다.
2. 정렬이 필요해보이고 작은수부터 나열하게끔 해줘야함
3. 스코빌 계산해서 배열 0번째 넣기

먼저 큐를 써야 겠다라는 생각도 일단 못했다.

우선 단순하게 Arrays.sort 를 하여 정렬을 해놓고 이중포문으로 해서 풀 수 있지 않을까? 라는 생각으로 접근

새로운 리스트를 생성해서 반복문 안에 있는 조건식을 통해 i + (j * 2)를 다시금 리스트에 넣어주려고 생각을 해봤지만

배열에서 원소를 빼서 연산한 값으로 바꿔치기를 하는 방법을 잘 모르겠다.

 

고민하다가 찾아보니 우선순위 큐를 사용해야 하는 문제였다.

작성한 코드

import java.util.*;

class Solution {

	public int solution(int[] scoville, int K) {

		int answer = 0;
		PriorityQueue<Integer> pq = new PriorityQueue<>();

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

		while (pq.peek() < K) {
			if (pq.size() < 2) { // 스코빌 지수를 만들 수 없는 경우
				return -1;
			}
			int food1 = pq.poll();
			int food2 = pq.poll();
			pq.add(food1 + 2 * food2);

			answer++;
		}

		return answer;
	}
}

---

필요 개념 정리

큐(Queue) - FIFO 선입 선출 구조로 먼저 들어간 놈이 먼저 나온다!

스택(Stack) - LIFO 선입 후출 구조로 먼저 들어간 놈이 나중에 나옴 / 즉 나중에 들어간놈이 먼저 나온다. (공평한 자료구조)

우선순위 큐(Priority Queue) - 가장 우선순위가 높은 데이터가 먼저 나온다.

 

우선순위 큐를 구현하는 방법

 - 단순히 리스트를 이용하여 구현

   (리스트에 데이터를 연달아 넣은 후 리스트에서 값을 꺼낼때는 데이터를 확인 후 가장 큰 값을 뽑는다!)

 - 힙(heap) 자료구조를 이용하여 구현

 

데이터 개수가 N개일 때의 구현방식 비교

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

리스트

• 데이터를 삽입할 때 단순히 연달아 데이터를 넣기 때문에 시간복잡도 1
• 삭제의 경우는 가장 높은 우선순위의 데이터를 찾아야 하기 때문에 시간복잡도 N

힙(heap)

• 데이터를 넣는 것과 빼는 경우 모두 최악의 경우여도 시간복잡도 logN을 충족한다
• 결국 단순히 N개의 데이터를 힙에 넣었다가 모두 빼내는 작업이 정렬과 동일하다.

힙 자료구조란? 완전 이진 트리 자료구조의 일종이다!

• 완전 이진 트리는 루트노드로 부터 시작되어 왼쪽 자식노드, 오른쪽 자식노드 순으로 데이터가 삽입된다.
• 힙 자료구조에서는 항상 루트노드(root node)를 제거
• 최소힙(min heap) - 루트노드가 가장 작은 값을 가짐 / 즉 가장 작은 값이 우선시되어 제거된다.
• 최대 힙(max heap) - 루트노드가 가장 큰 값을 가짐 / 즉 가장 큰 값이 우선시되어 제일먼저 제거된다.

여기서는 힙 자료구조의 개념은 간단하게 알고 넘어가도록 하자