[Kotlin] 백준 20529번 : 가장 가까운 세 사람의 심리적 거리 <Silver 1>

https://www.acmicpc.net/problem/20529

20529번: 가장 가까운 세 사람의 심리적 거리

Code

---

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val T = readLine().toInt()

    repeat(T) {
        val N = readLine().toInt()
        val MBTI = readLine().split(" ")
        
        var distance = 0
        if (MBTI.size < 33){
            distance = when(MBTI.size){
                1 -> 0
                2 -> calcDistance(MBTI[0], MBTI[1])
                else -> getDistance(MBTI)
            }    
        }
        
        bw.write(distance.toString() + "\n")

    }

    bw.flush()
    bw.close()
}

fun getDistance(MBTI: List<String>): Int {
    val size = MBTI.size
    var min = Int.MAX_VALUE
    for (i in 0 until size - 2) {
        for (j in i + 1 until size - 1) {
            for (k in j + 1 until size) {
                var localMin = calcDistance(MBTI[i], MBTI[j]) + calcDistance(MBTI[j], MBTI[k]) + calcDistance(MBTI[i], MBTI[k])

                if (localMin == 0) return 0
                else if (min > localMin) min = localMin
            }
        }
    }

    return min
}

fun calcDistance(Fir: String, Sec: String): Int {
    var count = 0

    for (i in 0 until 4) {
        if (Fir[i] != Sec[i]) count++
    }

    return count
}

---

 

문제의 로직을 떠올리는 것 까지는 쉽다. 하지만 이 문제의 핵심은 시간을 줄이는 것이다.

 

사실 시간을 줄이는 것이 핵심이라는 것은 대충 봐도 보인다. O(N^3)가 떡하니 있는데 무조건 시간이 오래 걸리는 것 처럼 보인다.

그렇다면 어떻게 줄일 수 있을까?

 

가장 떠올리기 쉬운 것은 값이 한번이라도 0이 나온다면 바로 종료시키는 것이다.

우리는 최솟값을 찾고있기 때문에 한번이라도 0이 나온다면 그것보다 작은 값은 존재할 수 없다. 그렇기 때문에 0이 나온다면 그 즉시 반복문을 종료시키면 된다

 

두번째 방법은 "비둘기집 원리"를 사용하는 것이다.

간단하게 설명하자면 "비둘기가 N마리, 집이 M개가 있을때 N>M 이라면 한 집에 2마리 이상 있는 집이 반드시 하나 이상 있다" 라는 원리이다. 뜬급없이 왠 비둘기집 원리를 얘기하나 싶을 수도 있다.

하지만, 이 문제에서 위 원리를 적용 가능하다. 

 

특정 조건일때 반드시 하나의 값이 나오는 경우가 뭐가 있을까?

바로 같은 값이 3개 이상 있을 때 이다. 같은 값 3개가 존재한다면 최솟값은 반드시 0이 된다.

 

그렇다면 같은 값이 3개 이상 있다는 것은 어떻게 알 수 있까?

"하나의 비둘기 집 안에 비둘기 3마리 이상이 반드시 있어야 한다"와 같은 소리이다. 그렇기 때문에 N > 2M 일 경우 반드시 세마리 이상 들어가있는 집이 반드시 하나 이상 있다. 

MBTI의 갯수는 총 16개. 그렇다면 33개 이상의 값이 존재한다면 반드시 중복되는 값이 3개 이상 존재한다.

 

그러므로 33개 이상일때는 반드시 0을 출력해야한다.

 

 

 

사실 비둘기집 원리는 아주 간단한 내용이다.

하지만, 문제에 적용시킨다는 아이디어를 떠올리기 어렵다.

생각보다 유용하고 쉬우니까 앞으로 잘 사용해보자.