[알고리즘] 백준 20364(부동산 다툼) {swift, python}

 

 

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

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을, 갈 수 없다면 처음 마주치는 점유된 땅의 번호를 출력한다.

 

 

 

풀이과정

1. 완전 이진트리는 Array로 표현이 가능합니다. 따라서 Dictionary로 해결하지 않고, count가 n + 1인 array를 만듭니다. (Trees생성)

2. 루트를 탐색합니다. 그리고 만약 루트가 이미 방문한적이 있다면(다른 오리가 점유하고 있다면) 이미 방문했던 index를 기록합니다.

3. 방문했건 안했건 간에 최 상위 루트로 움직입니다. (왜나하면 부동산 구매를 위해 가장 먼저 만나는 오리는 ind 0인 루트와 가깝기 때문에 계속해서 index를 갱신해야하기 때문입니다.)

4. 외부 기록했던 index가 존재할경우(부동산을 가졌던 오리를 만났을 경우) 이 값을 업데이트 합니다.

4.1 만약 부동산을 가진 오리를 만나지 못한 경우는 tree를 업데이트 합니다. 

 

 

전체 코드 

import Foundation

func sol() {
    let NM = readLine()!.split(separator: " ").map{Int($0)!}
    let N = NM[0]
    let M = NM[1]

    var trees = Array(repeating: false, count: N + 1)
    var pm = 0
    func check(_ ind: Int) {
        if ind == 0 {
            return 
        }
        
        if trees[ind] == true {
            pm = ind
        }
        check(ind / 2)
    }
    let res = (0..<M).map{ _ -> Int in 
        let cur = Int(readLine()!)!
        pm = 0
        check(cur)
        if pm == 0 {
            trees[cur] = true
        }
        return pm
    }
    print(res.map{String($0)}.joined(separator: " \n"))
}

sol()

 

 

import sys

def sol():
    res = []
    (n, m) = list(map(int, sys.stdin.readline().strip().split()))
    trees = [False] * (n + 1)
    fm = 0
    def check(ind: int) :
        nonlocal trees, fm
        if ind == 0 :
            return
        
        if trees[ind] == True :
            fm = ind
        check(ind // 2)
    
    for _ in range(m) :
        cur = int(sys.stdin.readline())
        fm = 0
        check(cur)
        if fm == 0 :
            trees[cur] = True
        res.append(fm)
    
    res = list(map(lambda x: str(x), res))
    print("\n".join(res))
sol()