[baekjoon] 백준 20364번(파이썬): 부동산 다툼

문제

20364번: 부동산 다툼

알고리즘

- 반복문을 통해 오리들이 원하는 땅을 가지도록 한다.

- 다른 오리가 점유된 땅을 밟는지 확인하기 위해 자신이 원하는 땅부터 루트 땅까지 이동하면서 확인한다.

- 다른 오리가 이미 점유한 땅을 밟았다면, 땅의 번호를 변수에 넣어둔다.

- 반복이 끝나고 난 후 다른 오리가 점유한 땅을 밟은 땅의 번호가 처음으로 밟는 땅으로, 그 땅의 번호를 출력한다.

- 다른 오리가 점유한 땅을 밟지 않았다면 원하는 땅을 점유하고 0을 출력한다.

코드

import sys

n, q = map(int, sys.stdin.readline().split())

visited = [0] * (n + 1) # 땅의 점유 여부

# 반복문을 통해 오리들이 원하는 땅을 가지도록 한다.
for i in range(q):
    tan = int(sys.stdin.readline())
    target = tan
    flag = 0 # 다른 오리의 점유된 땅의 번호

    # 반복문을 통해 원하는 땅에서 루트 땅까지 점유된 땅을 밟는지 확인
    while target != 1:

        # 점유된 땅을 밟을 경우
        if visited[target] >= 1:
            flag = target # 다른 오리의 점유된 땅의 번호를 초기화

        # 2로 나눠 루트 땅까지 이동
        target //= 2

    # 루트 땅까지 이동하면서 점유된 땅을 밟았다면
    if flag:
        print(flag) # 밟은 땅의 번호를 출력

    # 그게 아니라면 땅을 점유하고 0을 출력
    else:
        visited[tan] = 1
        print(0)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법