백준 20364 부동산 다툼 Kotlin (트리)

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

20364번: 부동산 다툼

문제

이진 트리 모양의 땅으로 이루어진 꽉꽉마을에는 오리들이 살고 있다. 땅 번호는 다음과 같이 매겨진다.

1. 루트 땅의 번호는 1이다.
2. 어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2 × K, 오른쪽 자식 땅의 번호는 2 × K + 1이다.

어느날 오리들끼리 부동산 다툼이 일어나서 꽉꽉마을 촌장 경완이가 해결책을 가져왔고, 그 내용은 다음과 같다.

1. 오리들을 한 줄로 대기시킨다. 맨 처음 오리들은 1번 땅에 위치해 있다.
2. 오리들이 서있는 순서대로 원하는 땅을 가지도록 한다.

만약, 한 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅이 있다면 막대한 세금을 내야 하는 이유로 해당 땅을 지나가지 못해 그 오리는 땅을 가지지 못한다. 오리가 원하는 땅까지 가는 길에는 오리가 원하는 땅도 포함된다.

경완이의 해결책대로 땅 분배를 했을 때 각 오리별로 원하는 땅을 가질 수 있는지, 가질 수 없다면 처음 마주치는 점유된 땅의 번호를 구해보자.

입력

첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N < 220, 1 ≤ Q ≤ 200,000)

두 번째 줄부터 차례로 Q개의 줄에 걸쳐 i+1번째 줄에는 i번째 오리가 원하는 땅 번호 xi가 주어진다. (2 ≤ xi ≤ N)

출력

Q개의 줄에 원하는 땅에 갈 수 있다면 0을, 갈 수 없다면 처음 마주치는 점유된 땅의 번호를 출력한다.

알고리즘 분류

• 트리

풀이

귀여운 덕덕이가 9라는 땅을 갖고 싶다고 하자.

그럼 덕덕이가 땅을 갖지 못하는 경우는?

다른 덕덕이가 9,4,2 땅을 가지고 있는 경우이다.

그럼 덕덕이가 9라는 땅을 갖고 싶을 때 2,4,9 땅을 어떻게 검사할 수 있을까?

1부터 9까지 찾아가는 것은 쉽지 않다.

반대로 9에서 1까지 찾아가는 것은?

2로 냅다 나누면 된다.

9/=2 혹은 9 >> 1 을 반복하면 된다.

만약에 2,4,9 모두 다른 덕덕이가 가지고 있다면 출력은 2가 되어야 한다.

따라서 9부터 1까지 탐색하면서 다른 덕덕이가 가지고 있는 가장 작은 숫자의 땅을 출력하면 된다.

 

다른 덕덕이가 땅을 갖고 있는지는 땅이 최대 2^20개이기 때문에 배열에 저장하긴 무리일 것 같고, Set에 담아두었다.

Set에 값을 담을 때에는 해당 덕덕이가 땅을 소유할 수 있을 때만!

코드

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

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n, q) = getIntList()
    val se = mutableSetOf<Int>()
    //solve
    repeat(q) {
        val origin = getInt()
        var num = origin
        var answer = 0
        while (num > 1) {
            if (se.contains(num)) answer = num
            num /= 2
        }
        write("$answer\n")
        if(answer==0) se.add(origin)
    }


    close()
}