문제
이진 트리 모양의 땅으로 이루어진 꽉꽉마을에는 오리들이 살고 있다. 땅 번호는 다음과 같이 매겨진다.
- 루트 땅의 번호는 1이다.
- 어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2 × K, 오른쪽 자식 땅의 번호는 2 × K + 1이다.
어느날 오리들끼리 부동산 다툼이 일어나서 꽉꽉마을 촌장 경완이가 해결책을 가져왔고, 그 내용은 다음과 같다.
- 오리들을 한 줄로 대기시킨다. 맨 처음 오리들은 1번 땅에 위치해 있다.
- 오리들이 서있는 순서대로 원하는 땅을 가지도록 한다.
만약, 한 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅이 있다면 막대한 세금을 내야 하는 이유로 해당 땅을 지나가지 못해 그 오리는 땅을 가지지 못한다. 오리가 원하는 땅까지 가는 길에는 오리가 원하는 땅도 포함된다.
경완이의 해결책대로 땅 분배를 했을 때 각 오리별로 원하는 땅을 가질 수 있는지, 가질 수 없다면 처음 마주치는 점유된 땅의 번호를 구해보자.
입력
첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N < 220, 1 ≤ Q ≤ 200,000)
두 번째 줄부터 차례로 Q개의 줄에 걸쳐 i+1번째 줄에는 i번째 오리가 원하는 땅 번호 xi가 주어진다. (2 ≤ xi ≤ N)
출력
Q개의 줄에 원하는 땅에 갈 수 있다면 0을, 갈 수 없다면 처음 마주치는 점유된 땅의 번호를 출력한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
import sys
owned = set()
n, q = map(int, sys.stdin.readline().split())
for i in range(q):
x = int(sys.stdin.readline())
node, isOwned, num = x, False, 0
while node > 0:
if node in owned:
isOwned = True
num = node
node //= 2
print(num)
if not isOwned:
owned.add(x)
|
cs |
땅의 개수가 최대 2^20 정도라 리스트를 사용해서 방문 체크를 하면 선언만 해도 시간초과일 거 같아서 set을 사용했다.
어떤 노드의 번호 X에 대해서 그 부모 노드의 번호는 X/2 라는 점을 이용해서 1까지 모든 부모 노드를 체크해주면 된다.
만약 모든 부모 노드(자기 자신도 포함)를 방문한 적이 없다면 방문처리를 해주면 된다.
반약 방문한 적이 있다면 num에 그 노드의 번호가 저장이 되는데 아래부터 체크하기 때문에 가장 먼저 만나는 노드의
번호가 저장된다.