알고리즘) 더 맵게(프로그래머스, 힙 활용, Java)

문제 설명

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

---

코드 작성

염두한 점

• scoville은 정렬된 상태라는 전제가 없기 때문에 처음에 heapify 과정을 거쳐야 한다.
• 최소힙을 구현하여 루트와 루트의 자식 중 더 작은 수를 섞는다. (`scoville[0] + scoville[childIdx] * 2`)
• 노드가 2개 이상이어야 섞을 수 있기 때문에 `size`가 2 이상일 때만 while문을 동작시킨다.
• 처음부터 최소값이 `K` 이상일 수 있다. (처음부터 조건에 만족할 수 있다. 이 경우 섞은 총 횟수는 `0`이다.)
• 배열로 직접 구현한 코드의 경우 추가 메모리를 사용하지 않게 하기 위해 기존 배열을 계속 재정렬하며 `size`라는 변수를 두어 마지막 인덱스를 점차 줄여나감으로써 배열이 줄어듦을 표현하고자 했다.
• 배열로 직접 구현한 코드의 경우 배열의 요소 수는 줄어드는 것을 전제로 하기 때문에 resize 기능은 불필요하다.

 

배열로 구현한 코드

public int solution(int[] scoville, int K) {
    int cnt = 0;
    boolean success = false;
    int size = scoville.length;

    for (int i = (scoville.length - 1) / 2; i >= 0; i--) {
        heapify(scoville, i, size - 1);
    }

    // 처음부터 통과될 경우
    if (scoville[0] >= K) {
        success = true;
    }

    // 하향식 heapify 실행
    // 이 때, 최소힙이기 때문에 정렬된 이후의 루트 노드값이 K보다 클 때까지 cnt 상승하며 반복
    while (!success && size > 1) {
        // 섞을 자식 노드 찾기(좌우 노드 중 더 작은값)
        int childIdx = 1;
        if (size > 2 && scoville[2] < scoville[1]) {
            childIdx = 2;
        }

        int val = scoville[0] + scoville[childIdx] * 2;

        delete(scoville, size - 1); // root 삭제
        size--;
        delete(scoville, size - 1);
        size--;
        add(scoville, val, size - 1);
        size++;

        heapify(scoville, childIdx, size - 1);
        heapify(scoville, 0, size - 1);

        cnt++;

        if (scoville[0] >= K) {
            success = true;
            break;
        }
    }

    if (!success) return -1;

    return cnt;
}

void heapify(int[] list, int idx, int lastIdx) {
    int child1 = idx * 2 + 1;
    int child2 = idx * 2 + 2;

    int targetIdx = idx;
    if (child1 <= lastIdx && list[child1] < list[targetIdx]) {
        targetIdx = child1;
    }

    if (child2 <= lastIdx && list[child2] < list[targetIdx]) {
        targetIdx = child2;
    }

    if (targetIdx != idx) {
        swap(list, targetIdx, idx);
        heapify(list, targetIdx, lastIdx);
    }
}

void swap(int[] list, int idx1, int idx2) {
    int val = list[idx1];
    list[idx1] = list[idx2];
    list[idx2] = val;
}

int delete(int[] list, int lastIdx) {
    int val = list[0];

    list[0] = list[lastIdx];
    heapify(list, 0, lastIdx - 1);

    return val;
}

void add(int[] list, int node, int lastIdx) {
    // 노드 수가 줄어들기 때문에 resize는 신경쓰지 않음
    list[lastIdx + 1] = node;

    int idx = lastIdx + 1;
    while (idx > 0) {
        int parentIdx = (idx - 1) / 2;

        if (list[parentIdx] > node) {
            swap(list, parentIdx, idx);
            idx = parentIdx;
        } else {
            break;
        }
    }
}

---

PriorityQueue를 이용한 코드

Cf. 최대힙: `new PriorityQueue<>(Collections.reverseOrder());

public int solution(int[] scoville, int K) {
    int cnt = 0;

    PriorityQueue<Integer> queue = new PriorityQueue<>();
    for (int n : scoville) {
        queue.add(n);
    }

    if (queue.peek() >= K) {
        return cnt;
    }

    while (queue.size() > 1) {
        int val0 = queue.remove();
        int val1 = queue.remove();
        queue.add(val0 + val1 * 2);
        cnt++;

        if (queue.peek() >= K) {
            break;
        }

        if (queue.size() <= 1) {
            return -1;
        }
    }

    return cnt;
}