[백준(BOJ)] 13397 구간 나누기 2 - 스위프트 (Swift)

[Gold IV] 구간 나누기 2 - 13397

문제 링크

성능 요약

메모리: 69560 KB, 시간: 12 ms

분류

이분 탐색, 매개 변수 탐색

제출 일자

2024년 1월 18일 12:25:15

문제 설명

N개의 수로 이루어진 1차원 배열이 있다. 이 배열을 M개 이하의 구간으로 나누어서 구간의 점수의 최댓값을 최소로 하려고 한다. 구간은 다음과 같은 조건을 만족해야 한다.

1. 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다.
2. 배열의 각 수는 모두 하나의 구간에 포함되어 있어야 한다.

구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다.

예를 들어, 배열이 [1, 5, 4, 6, 2, 1, 3, 7] 이고, M = 3인 경우가 있다.

이때, [1, 5], [4, 6, 2], [1, 3, 7]로 구간을 나누면 각 구간의 점수는 4, 4, 6점이 된다. 이때, 최댓값은 6점이다.

만약, [1, 5, 4], [6, 2, 1], [3, 7]로 구간을 나누었다면, 각 구간의 점수는 4, 5, 4점이 되고, 이때 최댓값은 5점이 된다.

두 경우 중에서 최댓값이 최소인 것은 5점인 것이고, 5점보다 최댓값을 작게 만드는 방법은 없다.

배열과 M이 주어졌을 때, 구간의 점수의 최댓값의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N)

둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 구간의 점수의 최댓값의 최솟값을 출력한다.

 

풀이

위의 문제는 구간의 점수를 기준으로 잡고 이분 탐색을 진행하면 됩니다. 구간의 점수를 넘었을 경우, 구간의 개수를 증가시켜주고, 최소값과 최대값을 방문한 값으로 초기화시켜주면서 진행시켜주었습니다.

 

여기서 주의할 점은 구간의 점수는 해당 구간의 최대값에서 최소값을 빼야하기 때문에, 최대값과 최소값을 갱신해주면서 계산해주어야 합니다.

 

만약 구간의 개수가 M보다 크다면 구간이 많아졌다는 것을 의미하므로 구간의 점수를 높여주고,
구간의 개수가 M보다 작거나 같으면 구간이 적어졌다는 것을 의미하므로 구간의 점수를 낮쳐주며 찾아줍니다.

 

가장 주의할 점은 해당 문제에선 구간의 점수를 저장해주면서 진행해주어야 합니다. 구하고자 하는 것은 구간이 최소값이나, 최대값이 아니라 구간의 점수이기 때문에, 이를 저장하지 않고 구간(left, right 등)을 출력하게 되면, 정답을 지나치고 다른 값을 출력할 수도 있기 때문입니다.

 

다음은 코드입니다.

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
let array = readLine()!.split(separator: " ").map { Int($0)! }
var (left, right, ans) = (0, array.max()! - array.min()!, Int.max)

while left <= right {
    let mid = (left + right) / 2
    var (min, max, count) = (10001, -1, 1)
    for i in 0..<array.count {
        if i == 0 {
            (min, max) = (array[i], array[i])
        } else {
            if array[i] < min { // 기존의 min보다 작은 값이 들어오면 값 변경
                min = array[i]
            }
            if array[i] > max { // 기존의 max보다 큰 값이 들어오면 값 변경
                max = array[i]
            }
            if (max - min) > mid {  // 구간의 점수가 mid를 넘으면 초기화
                count += 1
                (min, max) = (array[i], array[i])
            }
        }
    }

    if count > m {
        left = mid + 1
    } else {
        right = mid - 1
        if mid < ans {  // 지나치다가 정답을 놓칠 수 있기 때문에 정답 저장해둠
            ans = mid
        }
    }
}
print(m == 1 ? array.max()! - array.min()! : ans)