백준 2548 대표 자연수 Kotlin (이분 탐색)

문제 출처 : https://www.acmicpc.net/problem/2548

2548번: 대표 자연수

문제

정보초등학교의 연아는 여러 개의 자연수가 주어졌을 때, 이를 대표할 수 있는 대표 자연수에 대하여 연구하였다. 그 결과 어떤 자연수가 다음과 같은 성질을 가지면 대표 자연수로 적당할 것이라고 판단하였다.

“대표 자연수는 주어진 모든 자연수들에 대하여 그 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수이다.”

예를 들어 주어진 자연수들이 [4, 3, 2, 2, 9, 10]이라 하자. 이때 대표 자연수는 3 혹은 4가 된다. 왜냐하면 (4와 3의 차이) + (3과 3의 차이) + (2와 3의 차이) + (2와 3의 차이) + (9와 3의 차이) + (10과 3의 차이) = 1+0+1+1+6+7 = 16이고, (4와 4의 차이) + (3과 4의 차이) + (2와 4의 차이) + (2와 4의 차이) + (9와 4의 차이) + (10과 4의 차이) = 0+1+2+2+5+6 = 16으로 같으며, 이 두 경우가 차이들의 합을 최소로 하기 때문이다. 비교를 위하여 평균값인 5의 경우를 생각하여 보면, (4와 5의 차이) + (3과 5의 차이) + (2와 5의 차이) + (2와 5의 차이) + (9와 5의 차이) + (10과 5의 차이) = 1+2+3+3+4+5 = 18로 위의 두 경우보다 차이들의 합이 더 커짐을 볼 수 있다.

연아를 도와서 위의 성질을 만족하는 대표 자연수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 자연수의 개수 N이 입력된다. N은 1 이상 20,000 이하이다. 둘째 줄에는 N개의 자연수가 빈칸을 사이에 두고 입력되며, 이 수들은 모두 1 이상 10,000 이하이다.

출력

첫째 줄에 대표 자연수를 출력한다. 대표 자연수가 두 개 이상일 경우 그 중 제일 작은 것을 출력한다.

알고리즘 분류

• 브루트포스 알고리즘
• 정렬

풀이

문제를 보면 중앙 값을 출력하면 되는 것을 쉽게 알 수 있다.

따라서 정렬 후 중앙 값을 출력하는데, n이 짝수인 경우 

0 1 2 3 4 5, n = 6

중앙값이 2,3이 될 수 있으므로 n-1에 2를 나눈 것이 중앙 인덱스다.

따라서 정렬 후 arr[(n-1)/2]를 출력하기만 하면 끝이다.

 

하지만 본인은 코테를 임할 때 항상 완전 탐색이 가능한지 먼저 본다.

그리디하게 혹은 수학적으로 접근하는 것보다 우리는 컴퓨터의 빠른 연산을 이용해서 모두 검사해서 최적의 답을 도출하는 것이 내 입장에선 가장 머리를 덜 쓰고 푸는 것이다.

20000개에서 매번 대표 자연수를 선택하고 차이 값들을 더하는 것은 20000*20000으로 시간 초과.

좀 더 빠르게 탐색하려면? 이분 탐색을 이용하면 된다.

그럼 O(20000 * log20000)으로 문제를 풀 수 있다.

이분 탐색 풀이는 s = 0, e = n-1로 잡고 mid = (s+e)/2에 대해서 차이값들의 합을 구한 후 기존의 차이값들의 합보다 작거나 같다면 

기존 합을 갱신, 답을 갱신하고 이분 탐색의 왼쪽 구역을 탐색한다. 반대의 경우 오른쪽 구역을 탐색한다.

 

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun getSum(arr: IntArray, mid: Int): Int{
    var sum = 0
    for(i in arr){
        sum += Math.abs(arr[mid]-i)
    }
    return sum
}

fun main() = with(System.out.bufferedWriter()){

    //input
    val n = getInt()
    val input = getIntList().toIntArray()
    input.sort()
    //solve
    var s = 0
    var e = input.size-1
    var answer = 0
    var sum = Int.MAX_VALUE
    while(s<=e){
        val mid = (s+e)/2
        val result = getSum(input,mid)
        if(result <= sum){
            answer = input[mid]
            e = mid-1
            sum = result
        }else{
            s = mid+1
        }
    }
    write("$answer")
    close()
}