[Algorithm] 백준 - 1654번 랜선 자르기 (Swift)

아래와 같은 백준 문제를 풀다가 파라메트릭 서치라는 알고리즘을 알게 되었다. 이에 관해서 정리하려고 한다.
 

문제 요약

1654번: 랜선 자르기

 
문제를 간단히 요약하자면 주어진 K개의 랜선으로 N개를 만들 수 있는 랜선의 최대 길이를 구하는 문제이다. 예시를 들면 [802, 743, 457, 539] 로 4개의 랜선의 길이가 주어지고 이 랜선들로 11개의 랜선을 만들 수 있는 랜선의 최대 길이를 구하는 문제인 것이다.
 

처음 문제 풀이

아래처럼 아주 간단하게 랜선의 길이를 1부터 조건에 맞을 때 까지 반복문을 돌리는 것으로 생각했다. 하지만 이 방법에는 문제가 있다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수이다. 라는 조건이 있었는데 만약 최악의 경우 21억번보다 많은 반복 횟수를 돌려야 한다는 것이다. 당연히 아래와 같이 답변을 제출하면 런타임 오류가 난다.

func solution(_ lines: [Int], _ n: Int) {
    for i in 1...lines.min()! {
        var count = 0
        
        for line in lines {
            count += line / i
        }
        
        if count < n {
            print(i-1)
            break
        }
    }
}

 

파라메트릭 서치 (Parametric Search) 활용

그렇다면 어떻게 랜선의 최댓값을 찾을 수 있을까? 바로 파라메트릭 서치를 이용하여 구할 수 있다. 이진탐색을 이용하여 구현한다. 아래와 같은 코드로 구현했다. 어떠한 최댓값을 찾을때 처음에 범위를 정하고 그 범위에서 이진탐색의 방식으로 값에 접근한뒤 그 값을 참, 거짓으로 판별한후 다시 반복하는 형식이다. 좀더 효율적인 노가다를 컴퓨터에게 시키는 느낌이 들었다.

func solution(_ lines: [Int], _ n: Int) {
    var low = 1
    var high = lines.max()!
    
    while low <= high {
        let mid = (low + high) / 2
        var count = 0
        
        for line in lines {
            count += line / mid
        }
        
        if count >= n {
            low = mid + 1
        } else if count < n {
            high = mid - 1
        }
    }
    
    print(high)
}

 
이 문제에서 주의할 점은 (개인적으로) 목표 갯수의 전선이 나오는 값중 최댓값을 찾아야 한다는 점이다. 조건을 low <= high 로 할 것인지, low + 1 < high 로 할 것인지... low = mid 로 할 것인지 low = mid + 1 로 할 것인지에 따라 나오는 결과가 달라지는데 이 부분을 판단해야 한다. (나는 이부분에 대해서 아직 좀더 공부가 필요한 듯 싶다)