[프로그래머스] 더 맵게

1.  문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

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

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.

Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

2. 제한사항

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

3. 입출력예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

4. 풀이(과정 or 최종)

Solution 1

1. PriorityQueue를 사용하여 순서대로 Queue에 담아주었다. (작은 수부터 담긴다)

2. 새로운 스코빌 지수를 구현하여  Queue에 넣어준다.

3. Queue가 하나만 남을 때 까지 반복문을 돌려준다.

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        
        int answer = 0;
        int scv = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int s : scoville) pq.add(s);
        
        while(pq.size() > 1 && pq.peek() < K){
            int n1 = pq.poll();
            int n2 = pq.poll();
            scv = n1 + (n2 * 2);
            pq.add(scv);
            answer++;
        }
        
        return pq.peek() < K ? -1 : answer ;
    }
}

5. 풀이 설명

PriorityQueue를  heap 자료구조로 구현하였다.

PriorityQueue는 Queue와 마찬가지로 First in First Out 구조이고, 우선순위가 높은 데이터를 먼저 나오게 하는것이 특징이다.

heap은 완전이진트리로 부모노드가 자식노드보다 우선순위가 크다.

 

PriorityQueue를 heap으로 구현하는 이유?

배열로 구현하게 된다면 정렬이 되어있을 때 우선순위가 높은 데이터를 반환할 때 index를 활용하여 찾을 수 있어서 빠르다. 하지만 값을 삽입할 때 우선순위를 결정하기 위하여 모든 index를 탐색해야 하고, 중간인 값을 삽입하게 될 때는 뒤에 있는 데이터를 모두 뒤로 밀어야 하기 때문에 효율성이 좋지 않다.

시간 복잡도(n=자료의 개수) : 삭제 O(1), 삽입 : O(n)

 

연결리스트로 구현하게 된다면 우선순위가 높은 데이터를 반환하는 것은 쉽다. 하지만 중간값을 넣기 위하여 탐색 할 때 최악의 경우 모든 index를 다 탐색해야 할수도 있다.

시간 복잡도(n=자료의 개수) : 삭제 O(1), 삽입 : O(n)

 

힙으로 구현하게 된다면 삭제나 삽입 과정에서 모두 부모와 자식간의 비교로만 계속 이루어진다. 이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 갯수는 2배 증가하고, 비교 연산 횟수는 1회 증가한다.

시간 복잡도(n=자료의 개수) : 삭제 O(log2n), 삽입 O(log2n)

6. 결과 

Solution 1

7. 마치며

priorityQueue.. heap.. 처음 알았다! 처음에는 heap 메모리 말하는줄 알았다.

그래서 살짝 개념 정리 글도 적었다.

이제 대전 놀러갈것이다.. 좋은 하루!!