[파이썬 알고리즘 문제풀이 입문] 이분탐색(결정알고리즘) & 그리디 알고리즘 - 마구간 정하기

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ..., xN의 좌표를 가지며, 마구간 간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

def distance(mid):
    count = 1 # 제일 앞에는 무조건 있으니까
    start = min(xi)
    for i in range(1, N):
        if xi[i] - start >= mid:
            count += 1
            start = xi[i]
    return count    

N, C = map(int, input().split())
xi = [int(input()) for _ in range(N)]
xi.sort()

# 두 말 사이의 거리
lt = 1
rt = max(xi) # 맨뒷값을 넘지 않기 때문

while lt<=rt:
    mid = (lt+rt)//2
    if distance(mid) >= C:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1
print(res)

• 답안 : Kotlin (내가 바꿔본 것 / 정확X)

import java.io.*
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    val (N, C) = readLine().split(" ").map { it.toInt() }
    val xi : MutableList<Int> = mutableListOf()
    for(i in 0 until N) {
        xi.add(readLine().toInt())
    }
    var sorted_xi = xi.sorted()

    var lt = 1
    var rt = sorted_xi.max()
    var mid = 0
    var res = 0

    while(lt<= rt) {
        mid = (lt+rt)/2
        if(distance(mid, N, sorted_xi) >= C) {
            res = mid
            lt = mid + 1
        } else {
            rt = mid - 1
        }
    }
    println(res)
}

fun distance(mid : Int, N : Int, sorted_xi :List<Int>) : Int {
    var count = 1
    var start = sorted_xi.min()
    for(i in 1 until N) {
        if(sorted_xi[i]-start >= mid) {
            count += 1
            start = sorted_xi[i]
        }
    }
    return count
}

- 사용된 알고리즘은 이전 문제와 동일하게 이분탐색(결정 알고리즘)이 사용되었다.

- 좌표 값을 lt, rt로 잡을 생각으로 접근했는데, 두 말의 간격을 lt와 rt로 잡으면 된다는 것을 알게 되었다.