[백준][Kotlin] - 공정 컨설턴트 호석(22254)

문제 소개

🥇️ 문제 레벨 : 골드3
🔔 문제 유형 : 이분 탐색, 매개 변수 탐색, 우선 순위 큐
💬 풀이 언어 : Kotlin
🖇️ 문제 링크 : 백준 문제 링크

📝 문제

거듭된 창업 성공을 이룬 류진국 사장은 이번에는 맞춤형 선물을 제작해주는 공장을 만들기로 했다. 현재 들어온 맞춤형 선물 주문은 총 N개이며, 각 맞춤형 선물마다 제작에 필요한 시간이 정해져있다. 주문의 번호는 1번부터 N번까지 매겨져 있으며, 다음과 같은 규칙에 맞게 공정이 이뤄진다.

공정 라인이 총 K개가 있다면 1번부터 K번까지의 번호가 존재한다.
공정 라인의 사용 시간은 배정된 맞춤형 선물들의 제작 시간의 총합이다.
i번 선물은 1번 부터 i-1번 선물들이 배정된 이후에 사용 시간이 가장 적은 공정 라인 중 하나에 배정된다.

모든 맞춤형 선물의 제작이 완료될 때까지 최대 X시간이 남아있는 상황인데, 아직 공정 라인의 개수 K가 정해져 있지 않다. 류진국 사장은 이 분야 최고 권위자, 공정 컨설턴트 호석에게 의뢰했다. 공정 컨설턴트 호석은 최소한의 비용을 쓰기 위해서 공정 라인의 개수를 최소화 시키고자 한다. 호석을 도와 필요한 최소 공정 라인 개수를 계산하자.

🤔 문제 분석

우선 구해야하는 것은 공정 라인의 최소 개수(K)이다. K를 구하는 방법은 다양할 것이다.

방식1

1부터 N까지 직접 시도하기

K를 구하기 위해서 다음과 같이 완전 탐색을 하는 것이다.

for (i in 1..n) {
    // ...
}

하지만 이 문제의 제한 사항을 읽어보면 다음과 같다.

시간 제한 : 1초
1 <= N <= 100,000
1 <= X <= 10^9

완전 탐색의 경우 1 ~ 10만까지 돌면서 시뮬레이션을 돌려야한다. 이 시뮬레이션에서 우선 순위 큐를 사용한다고 가정하면, 다음과 같다.

선형 탐색 : n
n개 작업에 대한 시뮬레이션 : n log n
- 1 ~ n까지 우선 순위 큐에 삽입 : n
- 우선 순위 큐 내부 정렬 : log n

즉, n(선형 탐색) × n log n(시뮬레이션) = O(n² log n)의 시간 복잡도를 가지게 되어 시간 초과가 나게 된다. 따라서 바깥에서 n번 반복하는 구조가 아니라, 반복 횟수를 log n 수준으로 줄여봐야 한다.

방식2

이분 탐색을 통해 빠르게 찾기

탐색을 줄이기 위해서는 이분 탐색을 사용할 수 있다.

이분 탐색 : log n
n개 작업에 대한 정렬 연산 : n log n
- 우선 순위 큐에 삽입 : n
- 우선 순위 큐 내부 정렬 : log n

즉, log n(이분 탐색) x n log n(시뮬레이션) = O(n (log n)^2)으로 통과할 수 있게 된다.

이분 탐색

K를 구하기 위해 매개변수 탐색을 해야 한다. 기본적인 이분 탐색 형태를 띄지만 문제 유형에 매개 변수 탐색이 있는 만큼, mid를 통해 min(left), max(right)를 어떻게 구성할지 정해야 한다.

private fun binarySearch(n: Int, x: Int, times: IntArray): Int {  
    var min = 0  
    var max = n  

    while (min < max) {  
        val mid = (min + max) / 2  

        if (check(n, x, mid, times)) {  
            max = mid  
        } else {  
            min = mid + 1  
        }  
    }  

    return max + 1  
}

여기서 check 함수가 매개 변수 탐색에 대한 코드에 해당한다. 이 함수를 통해 mid의 수만큼의 공정 라인을 만들었을 때, x 만큼의 시간이 나올 수 있는지 판단하면 된다.

매개 변수 탐색(시뮬레이션)

0..mid : 0 ~ mid까지를 의미
0 until mid : 0 ~ mid - 1을 의미

private fun check(n: Int, x: Int, mid: Int, times: IntArray): Boolean {  
    val pq = PriorityQueue<Int>()  

    for (i in 0..mid) {  
        pq += times[i]  
    }  

    for (i in mid + 1 until n) {  
        val cur = pq.poll()  

        if (cur + times[i] > x) {  
            return false  
        }  
        pq += (cur + times[i])  
    }  

    return true  
}

여기서 mid를 K라고 이해하면 된다. 첫 번째 for문에서 0 ~ K개의 공정을 만드는 것이다. 예를 들어, mid가 3일 경우 0번, 1번, 2번, 3번 총 4개의 공정 라인을 만드는 것이다.

문제의 예제 입력을 기반으로 시뮬레이션을 이해해보자.

6 11
5 2 8 4 3 5

첫 번째 루프

binarySearch() -> min = 0, max = 6, mid = 3
check()
- 첫 번째 반복문(0 ~ 3) -> [5, 2, 8, 4]를 각 공정 라인에 배치한다.
  - 즉, 0번 라인 -> 2, 1번 라인 -> 4, 2번 라인 -> 5, 3번 라인 -> 8
    - PriorityQueue를 사용하기 때문에 작은 수부터 추가
    - 0번 라인, 1번 라인 등은 이해를 돕기 위한 예시이다.
- 두 번째 반복문(4 ~ 5)
  - 이제 각 라인에 다른 선물을 처리하는 시간을 더해준다.
  - 0번 라인 -> 2 + times[4] -> 3의 값인 5를 다시 pq에 추가해준다.
  - 1번 라인 -> 4 + times[5] -> 5의 값인 9를 다시 pq에 추가해준다.
- 더 이상 탐색할게 없으니 true를 반환

이 때, 최종 PriorityQueue에는 다음과 같이 들어있을 것이다. 여기서 대괄호 안의 수는 n번 선물을 의미한다.

0번 라인 -> 5(2[2] + 3[5])
1번 라인 -> 8(4[4] + 5[6])
2번 라인 -> 5(5[1])
3번 라인 -> 8(8[3])

두 번째 루프

이전 루프에서 true가 나왔으니, max = mid 연산을 진행한다.

binarySearch() -> min = 0, max = 3, mid = 1
check()
- 첫 번째 반복문(0 ~ 1) -> [5, 2]를 각 공정 라인에 배치한다.
  - 즉, 0번 라인 -> 2, 1번 라인 -> 5
- 두 번째 반복문(2 ~ 5)
  - 이제 각 라인에 다른 선물을 처리하는 시간을 더해준다.
  - 0번 라인 -> 2 + times[2] -> 8의 값인 10을 다시 pq에 추가해준다.
  - 1번 라인 -> 5 + times[3] -> 4의 값인 9를 다시 pq에 추가해준다.
  - 1번 라인 -> 9 + times[4] -> 3의 값은 11을 초과하기에 pq에 추가하지 않고, false를 반환한다.

이 때, 최종 PriorityQueue에는 다음과 같이 들어있을 것이다.

0번 라인 -> 10(2[2] + 8[3])
1번 라인 -> 9(5[1] + 4[4])

세 번째 루프

이전 루프에서 false가 나왔으니, min = mid + 1 연산을 진행한다.

binarySearch() -> min = 2, max = 3, mid = 2
check()
- 첫 번째 반복문(0 ~ 2) -> [5, 2, 8]을 각 공정 라인에 배치한다.
  - 즉, 0번 라인 -> 2, 1번 라인 -> 5, 2번 라인 -> 8
- 두 번째 반복문(3 ~ 5)
  - 이제 각 라인에 다른 선물을 처리하는 시간을 더해준다.
  - 0번 라인 -> 2 + times[3] -> 4의 값인 6을 다시 pq에 추가해준다.
  - 1번 라인 -> 5 + times[4] -> 3의 값인 8을 다시 pq에 추가해준다.
  - 0번 라인 -> 6 + times[5] -> 5의 값인 11을 다시 pq에 추가해준다.
- 더 이상 탐색할게 없으니 true를 반환

이 때, 최종 PriorityQueue에는 다음과 같이 들어있을 것이다.

0번 라인 -> 11(2[2] + 4[4] + 5[6])
1번 라인 -> 8(5[1] + 3[5])
2번 라인 -> 8(8[3])

네 번째 루프