[백준][Python] 20364번 부동산 다툼

20364번: 부동산 다툼

 

코드

import sys
n,q = map(int,input().split())
num = []
vis = set()
for _ in range(q):
    a = int(sys.stdin.readline().rstrip())
    num.append(a)

def visit(a):
    ans = 0
    b = a
    while b > 0:
        if b in vis:
            ans = b
        b//=2
    if ans == 0:
        vis.add(a)
    print(ans)
    
for i in num:
    visit(i)

 

설명

처음에 vis를 리스트로 했더니 시간초과가 떠서 set으로 바꿔주었다. 

자식노드의 번호는 이미 정해져있기 때문에 오리가 원하는 땅을 기준으로 위로 거슬러 올라갔다. 올라갈 때 부모 노드는 2로 나눈 값이기 때문이다. 거슬러 올라가기 때문에 처음 마주치는 점유된 땅은 코드 상으로는 가장 마지막에 만나는 값이다. 따라서 점유된 땅 번호를 계속 갱신시켜줘야 한다. 만약 num=0일 때, 즉 원하는 땅을 가질 수 있을 때는 vis에 값을 추가시켜준다.