programmers) 더 맵게

프로그래머스  | 더 맵게

이번에는 프로그래머스의 더 맵게 문제를 풀어보았다.

문제 링크는 아래와 같다.

👉프로그래머스 더 맵게 문제

---

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶어 한다.

이때 스코빌 지수가 가장 낮은 두 개의 음식을 골라 아래 방식으로 섞는다.

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

이 과정을 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복해야 한다.

만약 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없다면 -1을 반환해야 한다.

---

입출력 예시

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

예시를 직접 따라가 보면 다음과 같다.

처음 음식의 스코빌 지수는 아래와 같다.

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

가장 맵지 않은 음식 1과 두 번째로 맵지 않은 음식 2를 섞는다.

1 + (2 * 2) = 5

그러면 음식 목록은 다음과 같이 된다.

[5, 3, 9, 10, 12]

아직 가장 작은 값이 3이므로 K = 7보다 작다.

다시 가장 작은 두 값인 3과 5를 섞는다.

3 + (5 * 2) = 13

그러면 음식 목록은 다음과 같이 된다.

[13, 9, 10, 12]

이제 모든 음식의 스코빌 지수가 7 이상이 되었으므로 섞은 횟수는 2가 된다.

---

문제 유형 분류

이 문제는 힙, 우선순위 큐 문제이다.

처음에는 단순히 배열을 정렬한 뒤 작은 값부터 차례대로 섞으면 될 것 같다고 생각했다.

하지만 이 문제는 단순 정렬만으로는 해결하기 어렵다.

이유는 음식을 섞어서 만든 새로운 스코빌 지수도 다시 음식 목록에 들어가기 때문이다.

즉, 매번 아래 작업을 반복해야 한다.

1. 가장 작은 값 2개를 꺼낸다.
2. 새 스코빌 지수를 만든다.
3. 새 값을 다시 넣는다.
4. 다시 가장 작은 값을 확인한다.

그래서 매번 가장 작은 값을 빠르게 꺼낼 수 있는 PriorityQueue를 사용해야 한다.

---

입력 범위 확인

제한 사항은 다음과 같다.

scoville의 길이는 2 이상 1,000,000 이하
K는 0 이상 1,000,000,000 이하
scoville의 원소는 각각 0 이상 1,000,000 이하
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1 반환

scoville의 길이가 최대 1,000,000이므로, 매번 배열을 정렬하거나 모든 값을 반복해서 탐색하는 방식은 비효율적이다.

처음 한 번 정렬하는 것도 부족하다.
새로 만든 값이 다시 들어가기 때문에, 매번 가장 작은 두 값을 빠르게 찾을 수 있어야 한다.

---

시간 복잡도 허용선 판단

입력 크기가 최대 1,000,000이므로 O(N^2) 방식은 사용할 수 없다.

우선순위 큐를 사용하면 값을 넣거나 꺼낼 때 O(log N)이 걸린다.

각 음식을 큐에 넣고, 섞는 과정에서도 poll()과 offer()를 사용하므로 전체 시간 복잡도는 O(N log N)으로 볼 수 있다.

이 정도면 입력 범위 내에서 적절한 풀이 방식이라고 판단했다.

---

처음 접근에서 놓친 점

처음에는 배열을 정렬해서 작은 값부터 순서대로 더해가면 될 것 같았다.

하지만 이 방식은 문제의 실제 섞는 과정과 다르다.

예를 들어 아래와 같은 경우를 생각해볼 수 있다.

[1, 2, 3, 4, 100], K = 10

단순히 정렬된 배열에서 앞에서부터 누적하면,

1 + 2 * 2 = 5
5 + 3 * 2 = 11

이렇게 생각할 수 있다.

하지만 실제 문제에서는 섞은 값 5가 다시 음식 목록에 들어간다.

실제 과정은 다음과 같다.

1과 2를 섞음 → 5
남은 음식: [3, 4, 5, 100]

3과 4를 섞음 → 11
남은 음식: [5, 11, 100]

5와 11을 섞음 → 27
남은 음식: [27, 100]

즉, 새로 만들어진 값도 다시 비교 대상이 되기 때문에 단순 정렬 후 순차 처리로는 안 된다.

이 부분 때문에 이 문제는 정렬 문제가 아니라 우선순위 큐 문제라고 볼 수 있다.

---

사용할 자료구조: PriorityQueue

Java의 PriorityQueue는 기본적으로 작은 값이 먼저 나오는 최소 힙 구조이다.

PriorityQueue<Long> pq = new PriorityQueue<>();

이 문제에서는 매번 가장 맵지 않은 음식 2개를 꺼내야 하므로 PriorityQueue가 잘 맞는다.

사용한 주요 메서드는 다음과 같다.

offer() : 큐에 값 넣기
poll()  : 가장 작은 값 꺼내기
peek()  : 가장 작은 값 확인하기

---

풀이 방향

풀이 흐름은 다음과 같다.

1. PriorityQueue를 만든다.
2. scoville 배열의 값을 모두 PriorityQueue에 넣는다.
3. 가장 작은 값이 K 이상이면 종료한다.
4. 가장 작은 값이 K보다 작으면 가장 작은 값 2개를 꺼낸다.
5. 문제의 공식대로 새 스코빌 지수를 만든다.
6. 새 값을 다시 PriorityQueue에 넣는다.
7. 섞은 횟수를 증가시킨다.
8. 더 이상 섞을 수 없는데 K 미만이면 -1을 반환한다.

핵심 조건은 다음과 같다.

while (pq.size() >= 2 && pq.peek() < K)

음식이 2개 이상 있어야 섞을 수 있고, 가장 작은 값이 K보다 작을 때만 섞으면 된다.

---

최종 코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int cnt = 0;
        PriorityQueue<Long> pq = new PriorityQueue<>();

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

        while (pq.size() >= 2 && pq.peek() < K) {
            Long first = pq.poll();
            Long second = pq.poll();

            Long result = first + (second * 2);
            pq.offer(result);

            cnt++;
        }

        if (pq.peek() < K) {
            return -1;
        }

        return cnt;
    }
}

---

코드 설명

먼저 PriorityQueue를 생성한다.

PriorityQueue<Long> pq = new PriorityQueue<>();

PriorityQueue는 기본적으로 작은 값이 먼저 나오기 때문에, 이 문제에서 가장 작은 스코빌 지수를 꺼내기에 적합하다.

그 다음 scoville 배열의 값을 모두 큐에 넣는다.

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

여기서는 Long을 사용했다.

스코빌 지수를 섞는 과정에서 값이 커질 수 있기 때문에 int보다 Long으로 처리하는 것이 더 안전하다고 생각했다.

이후 가장 작은 값이 K보다 작고, 음식이 2개 이상 남아 있으면 계속 섞는다.

while (pq.size() >= 2 && pq.peek() < K)

반복문 안에서는 가장 작은 값 2개를 꺼낸다.

Long first = pq.poll();
Long second = pq.poll();

그리고 문제에서 주어진 공식대로 새 스코빌 지수를 만든다.

Long result = first + (second * 2);

만든 값을 다시 우선순위 큐에 넣는다.

pq.offer(result);

한 번 섞었으므로 횟수를 증가시킨다.

cnt++;

반복이 끝난 후에도 가장 작은 값이 K보다 작다면, 더 이상 모든 음식을 K 이상으로 만들 수 없다는 뜻이므로 -1을 반환한다.

if (pq.peek() < K) {
    return -1;
}

---

예외 케이스

이 문제에서 주의해야 할 예외 케이스는 더 이상 섞을 수 없는 경우이다.

예를 들어 음식이 하나만 남았는데 그 값이 아직 K보다 작다면 더 이상 두 음식을 섞을 수 없다.

그래서 반복문의 조건에 pq.size() >= 2를 넣었다.

while (pq.size() >= 2 && pq.peek() < K)

그리고 반복문이 끝난 뒤에도 가장 작은 값이 K보다 작으면 -1을 반환한다.

if (pq.peek() < K) {
    return -1;
}

---

시간 복잡도

scoville의 길이를 N이라고 하면, 먼저 모든 값을 우선순위 큐에 넣는다.

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

offer()는 한 번에 O(log N)이 걸리므로, 전체 삽입은 O(N log N)으로 볼 수 있다.

이후 섞는 과정에서는 매번 아래 연산을 수행한다.

poll()
poll()
offer()

각 연산은 O(log N)이고, 최악의 경우 여러 번 반복될 수 있다.

따라서 전체 시간 복잡도는 다음과 같다.

시간 복잡도: O(N log N)

참고로 Java의 PriorityQueue에 한 번에 넣는 방식이 아니라 하나씩 offer()를 사용했기 때문에 삽입 과정도 O(N log N)으로 정리했다.

---

공간 복잡도

모든 스코빌 지수를 PriorityQueue에 넣기 때문에 입력 크기만큼의 추가 공간이 필요하다.

따라서 공간 복잡도는 다음과 같다.

공간 복잡도: O(N)

---

복잡도 정리

시간 복잡도: O(N log N)
공간 복잡도: O(N)

---

이번 풀이에서 배운 점

이번 문제를 풀면서 가장 크게 배운 점은 한 번 정렬하는 것과 우선순위 큐를 사용하는 것은 다르다는 것이다.

처음에는 정렬을 한 뒤 앞에서부터 차례대로 처리하면 될 것 같았다.

하지만 이 문제는 새로 만든 스코빌 지수가 다시 음식 목록에 들어가고, 그 값도 다시 가장 작은 값 후보가 된다.

그래서 매번 가장 작은 값 2개를 빠르게 꺼낼 수 있는 PriorityQueue를 사용해야 했다.

또 PriorityQueue에 배열 값을 넣는 방법도 다시 연습할 수 있었다.

PriorityQueue<Long> pq = new PriorityQueue<>();

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

이번 문제를 통해 정렬 문제처럼 보이더라도, 반복적으로 최소값이나 최대값을 꺼내야 한다면 힙이나 우선순위 큐를 떠올려야 한다는 것을 알게 되었다.

 

반대로 최대 힙을 꺼내야한다면, 아래와 같이 선언하자.

PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());

 

---

셀프 체크

왜 처음에 바로 풀지 못했는가?

처음에는 한 번 정렬한 뒤 작은 값부터 차례대로 섞으면 된다고 생각했다.

하지만 이 문제는 섞어서 만든 값이 다시 음식 목록에 들어가기 때문에, 단순 정렬만으로는 해결할 수 없었다.

시간이 부족했는가?

문제 풀이 자체보다 자료구조 선택에서 시간이 걸렸다.

정렬과 우선순위 큐의 차이를 생각하는 데 시간이 필요했다.

문제 해석을 잘못했는가?

처음에는 “가장 작은 값부터 섞는다”는 부분만 보고 정렬을 떠올렸다.

하지만 중요한 조건은 “섞은 음식도 다시 음식 목록에 포함된다”는 점이었다.

자료구조 선택을 잘못했는가?

처음에는 배열 정렬을 사용하려고 했다.

하지만 매번 가장 작은 값 2개를 꺼내야 하기 때문에 PriorityQueue가 더 적절했다.

엣지 케이스를 놓쳤는가?

더 이상 섞을 수 없는 경우를 주의해야 했다.

음식이 1개만 남았는데 아직 K보다 작다면 -1을 반환해야 한다.

구현 실수가 있었는가?

처음에는 Integer와 Long 타입을 섞어서 사용하면서 오류가 났다.

PriorityQueue<Long>을 사용한다면 poll()로 꺼낸 값도 Long으로 받아야 한다.

또 변수명 오타나 괄호 실수도 있었기 때문에, 최종 제출 전에는 컴파일 오류가 없는지 확인하는 습관이 필요하다고 느꼈다.

시간 복잡도 판단을 잘못했는가?

처음에는 정렬 한 번으로 해결할 수 있다고 생각했지만, 실제로는 매번 최소값을 다시 찾아야 했다.

그래서 O(N log N)으로 동작하는 우선순위 큐 풀이가 필요했다.