Baekjoon 백준 알고리즘 - 부동산다툼 ( 20364 )

1.문제소개

• 트리 유형의 문제다
• 이진 트리 배열의 구조를 알면 좋다.
• 입력 노드( 예제에서는 입력된 오리의 위치) 까지의 탐색 경로 중에, 이미 방문 ( 예제에서는 오리의 집 선점) 된 노드가 있다면 가장 처음 마주치는 노드를 출력하고, 아니면 0 을 출력하는 문제다. 

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

2.코드

import sys

def inputCase():
    N,Q = sys.stdin.readline().split(' ')
    N,Q  = int(N),int(Q)
    ducks = []
    for i in range(0,Q):
        ducks.append(int(sys.stdin.readline()))

    return N,Q,ducks

def getParentNode(childNode):
    return (childNode)//2
        
def solution():
    # 입력 전처리
    N,Q,ducks = inputCase()

    BT_F = [False for x in range(0,N+1)] # 이진 트리 배열, 오리의 땅의 점유 여부를 체크

    for e in ducks:
        p = e
        hasLand = False
        preDuckLoc = 0
        
        while(p>1):

            if BT_F[p] == True:
               hasLand = True
               preDuckLoc = p
            
            p = getParentNode(p) 

        if hasLand:
            print(preDuckLoc)
        else:
            print(preDuckLoc)
            BT_F[e]=True


solution()

3.코멘트

• 처음 제출한 알고리즘이 틀렸는데도, 백준에서는 시간 초과로 출력이 됐다. 
• 해당 문제는 기본 입력 함수인 input() 을 이용할 경우 시간 초과로 출력이 되며, 성능면에서 더 빠른 sys 패키지 내 readline() 을 이용해야 한다 . ( 함께 스터디한 재민님에 의해 알게 됐다.)
• 처음에 부모 노드의 방문 체크만 해서 틀렸는데, 이 역시 스터디를 통해 해결 할 수 있었다.