[프로그래머스] 더 맵게

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

문제는 위와 같으며, 이 문제는 최소힙을 사용하여 해결할 수 있습니다.

 

힙(Heap)이란,

최솟값 또는 최댓값을 빠르게 찾기 위한 완전이진트리 형태로 만들어진 자료구조입니다.

 

완전이진트리는 모든 노드의 차수를 최대 2로 제한한 이진트리에서

1. 마지막 노드를 제외한 모든 노드가 채워져 있어야 하고

2. 모든 노드가 왼쪽부터 채워져 있어야 한다는

조건을 추가로 만족하는 트리를 말합니다.

완전 이진 트리로 새로 값이 추가되면 6의 오른쪽 자식 노드로 추가됩니다.

 

힙은 완전이진트리 구조를 특정 조건을 주면서 채워나가는 자료구조이며 대표적으로 최소 힙과 최대 힙이 있습니다.

 

최소 힙의 경우 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같다는 조건을 가지고,

최대 힙은 이와 반대로 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같다는 조건을 가지고 있습니다.

 

힙을 구현할 때는 주로 배열을 사용합니다. 배열을 사용하게 되면 인덱스를 사용하여 부모 노드와 자식 노드의 위치를 표현할 수 있습니다.

 

✔️ 부모 노드의 인덱스 = 자식 노드의 인덱스 / 2
✔️ 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
✔️ 오른쪽 자식 노드의 인덱스 = (부모 노드의 인덱스 * 2 ) + 1

배열에 저장 시 인덱스 혼동을 줄이기 위해 0에는 임의의 0값을 저장하고 실제 데이터는 인덱스 1부터 저장합니다.

 

여기에서는 최소 힙에 데이터를 추가하고 삭제하는 방법을 알아보겠습니다.

 

최소 힙에 데이터를 추가할 때는

1. 가장 마지막에 데이터를 추가

2. 추가된 데이터와 부모 노드의 값을 비교하여 추가된 데이터의 값이 더 작은 경우 부모 노드의 값과 추가된 노드의 값을 변경(swap)

3. 추가된 노드의 인덱스를 부모 노드의 인덱스와 바꾼 뒤 이 인덱스가 루트 노드가 아닌 경우 다시 2 ~ 3 과정을 반복

 

최소 힙에서 데이터를 삭제할 때는

1. 루트 노드의 값을 삭제 (따로 저장해두기)

2. 가장 마지막 노드를 루트 노드에 저장하고 마지막 노드 삭제

3. 자식 노드가 있을 때, 왼쪽 자식만 있는 경우 왼쪽 자식 노드를 선택하고 오른쪽 자식도 있는 경우는 두 자식 노드의 값을 비교하여 더 작은 값 선택

4. 선택된 자식 노드와 부모 노드를 비교하여 자식 노드가 부모 노드보다 작은 경우 값을 변경(swap)

5. 부모 노드의 인덱스를 자식 노드의 인덱스와 바꾼 뒤 더 이상 자식 노드가 없을 때까지 3 ~ 5 과정을 반복

---

다시 문제를 살펴보면, 주어진 K보다 모든 음식의 스코빌 지수가 높을 때까지 음식을 섞는 횟수를 구하는 것이므로

• 먼저 모든 음식을 최소 힙에 저장합니다. 그런 다음 아래 과정을 반복합니다.
•  최소 힙에서 음식을 하나 선택합니다. (최소 힙이기 때문에 가장 맵지 않은 음식이 선택됩니다.)
• 만약 최소 힙이 비어있다면, 모든 음식의 스코빌 지수가 K보다 높아질 수 없기 때문에 반복을 종료하고 -1을 반환합니다.
• 힙이 비어있지 않다면 처음 선택한 음식의 스코빌 지수를 K와 비교합니다.
  • 가장 맵지 않은 음식의 스코빌 지수가 K보다 크거나 같은 경우는 모든 음식의 스코빌 지수가 K보다 크거나 같은 것이므로 음식을 섞은 횟수를 반환하고 종료합니다.
  • 가장 맵지 않은 음식의 스코빌 지수가 K보다 작은 경우 최소 힙에서 음식을 하나 더 선택합니다. (두번째로 맵지 않은 음식 선택)
    • 만약 두번째로 맵지 않은 음식이 존재하지 않는다면, 이 경우는 음식을 섞을 수 없기 때문에 -1을 반환하며 반복을 종료합니다.
    • 두번째로 맵지 않은 음식이 존재한다면, 첫번째로 맵지 않은 음식 + (두번째로 맵지 않은 음식 * 2) 값을 구해 최소 힙에 저장하고 음식을 섞은 횟수를 증가시킵니다.

 

최소힙을 구현하여 문제를 풀면 다음과 같습니다.

import java.util.ArrayList;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;

        MinHeap foodScoville = new MinHeap();

        for (int s : scoville) {
            foodScoville.insert(s);
        }

        while (true) {
            int first = foodScoville.delete();

            // 최소 힙이 비어있는 경우
            if (first == 0) {
                break;
            }

            // 가장 맵지 않은 음식의 스코빌 지수가 목표 스코빌 지수보다 작은 경우 (섞을 필요가 있음)
            if (first < K) {
                int second = foodScoville.delete();

                if (second == 0) {
                    return -1;
                }

                foodScoville.insert(first + (second * 2));
                answer++;
            } else {  // 모든 음식의 스코빌 지수가 목표 스코빌 지수의 이상이 된 경우 종료
                return answer;
            }
        }

        return -1;
    }
    
    private static class MinHeap {
        private ArrayList<Integer> minHeep;

        public MinHeap() {
            this.minHeep = new ArrayList<>();
            this.minHeep.add(0);
        }

        // 최소 힙에 숫자 추가
        public void insert(int num) {
            minHeep.add(num);  // 가장 마지막에 우선 숫자 추가
            int idx = minHeep.size() - 1;  // 가장 마지막 인덱스 구하기

            // 루트로 이동하면서 부모 노드가 자식 노드보다 작은 경우 swap
            while (idx > 1 && minHeep.get(idx / 2) > minHeep.get(idx)) {
                int tmp = minHeep.get(idx);
                minHeep.set(idx, minHeep.get(idx / 2));
                minHeep.set(idx / 2, tmp);

                idx = idx / 2;  // 부모 인덱스로 이동
            }
        }

        // 최소 힙에서 루트 삭제
        public int delete() {
            // 힙에 더이상 값이 없는 경우
            if (minHeep.size() - 1 < 1) {
                return 0;
            }

            // Heap에서 최소값 뽑기
            int popMinValue = minHeep.get(1);

            // 루트에 가장 마지막 값을 넣고 마지막 값은 삭제
            minHeep.set(1, minHeep.get(minHeep.size() - 1));
            minHeep.remove(minHeep.size() - 1);

            // 다시 최소 힙 만들기
            int idx = 1;
            while ((idx * 2) < minHeep.size()) {
                // 먼저 왼쪽 자식을 변경할 자식으로 지정
                int childIdx = idx * 2;
                int child = minHeep.get(childIdx);

                // 만약 오른쪽 자식이 존재하고 오른쪽 자식이 왼쪽 자식보다 작은 경우
                // 변경할 자식을 오른쪽 자식으로 지정
                if (childIdx + 1 < minHeep.size() && child > minHeep.get(childIdx + 1)) {
                    childIdx += 1;
                    child = minHeep.get(childIdx);
                }

                // 부모 노드가 자식 노드보다 작은 경우 종료
                if (minHeep.get(idx) < child) {
                    break;
                }

                // 부모 노드와 자식 노드 swap
                int tmp = minHeep.get(idx);
                minHeep.set(idx, child);
                minHeep.set(childIdx, tmp);

                idx = childIdx;
            }

            return popMinValue;
        }
    }
}

 

Java에서 제공하는 PriorityQueue를 사용하여 문제를 풀 수 있습니다.

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;

        // 우선순위 큐를 생성
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        // 모든 음식의 스코빌 값을 우선순위 큐에 저장
        for (int i : scoville) {
            queue.offer(i);
        }

        // 우선순위 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            int first = queue.poll();  // 가장 맵지 않은 음식을 선택

            // 가장 맵지 않은 음식의 스코빌이 목표 스코빌보다 작은 경우
            if (first < K) {
                // 두번째로 맵지 않은 음식이 없는 경우 종료
                if (queue.isEmpty()) {
                    return -1;
                }

                int second = queue.poll();  // 두번째로 맵지 않은 음식을 선택
                queue.offer(first + (second * 2));  // 음식을 섞은 뒤 다시 저장
                answer++;  // 음식 섞은 횟수 증가
            } else {  // 가장 맵지 않은 음식의 스코빌이 목표 스코빌보다 크거나 같은 경우 모든 음식의 스코빌이 목표보다 크거나 같다는 것을 의미하므로
                return answer;  // 음식을 섞은 횟수 반환
            }
        }

        return -1;
    }
}