[Python/백준] 20364. 부동산 다툼

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

이진 트리

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

---

풀이

1차 풀이, 실패

import sys
input = sys.stdin.readline

# 이진 트리
# 루트 땅은 1번
# 방 번호는 그냥 완전 이진 트리 인덱스대로임.
# 오리들이 1번 땅에서 출발할건데,

# 입력 : 땅 개수 n, 오리 수 Q
# N 100만
# 2번째 줄부터 Q개의 줄 동안 i줄에 i번째 오리가 원하는 땅 번호 xi

# 출력 : Q개의 줄을 출력할건데, 갈 수 있으면 0, 못 가면 처음 마주치는 점유된 땅 번호.

# 이거 dfs + 백트래킹 쓰면 될 것 같은데? => 안됨. q*O(V + E) 시간 터짐.
# 원하는 땅 번호 배열 x[]
# 뭔가 올라올라가거나 내려나려가는거 하면 q*logn 돼서 될거같은데?
# 그냥 타고 내려가면서 그 길이 False인지 check하고,
# 만약 True이면 그 index 반환하면 될듯.
# 즉, 자식 노드를 주렁주렁 달고 있는 식으로 하면 될듯함.

n, q = map(int, input().split())
x = [int(input()) for _ in range(q)]
visited = [False] * (n + 1)

tree = [[-1, -1] for _ in range(n + 1)]
for i in range(1, n + 1):
    if 2*i <= n:
        tree[i][0] = 2*i
        if 2*i + 1 <= n:
            tree[i][1] = 2*i + 1

# 아니 근데, x[i]가 왼쪽길 오른쪽길 어디에 속해있는지 어케 알지?
# 5로 가고싶으면 처음에 2 3 어디로 갈지 어케알아??
# 결국 거꾸로 밑에서 위로 오긴 해야겠는데??

정답 확인 후 2차 풀이

시간복잡도 O(qlog(n))

이거 백준이니까 그냥 한 줄씩 받아서 바로바로 target 처리해도 되긴 함.

import sys
input = sys.stdin.readline

n, q = map(int, input().split())
x = [int(input()) for _ in range(q)]
visited = [False] * (n + 1)

# 결국 밑에서 위로 오긴 해야하고, // 연산자가 나머지 버려버려서 그냥 바로 부모를 찾아준다는 걸 생각하자.
# 결국 끝까지 올라가면서 틀렸는지 확인해야하니 문제 있으면 temp에 뭔가 넣어놓고,
# 마지막에 문제 있는 놈을 출력하도록 하면 됨.
# 그 끝까지 올라가는건, 그 수가 >1일 때로 while 돌리면 되고.

for target in x:
    temp = -1
    t = target
    while t > 1:
        if visited[t]:
            temp = t
        t //= 2

    if temp == -1:
        print(0)
        visited[target] = True
        continue
    print(temp)

# result에 다 append한 다음 아래처럼도 가능
# print("\n".join(map(str, result)))