SWEA 5176 이진탐색 (파이썬)

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

---

아이디어

1. 처음엔 어떻게 접근해야 할지 조차 몰랐다.
2. 답은 1부터N까지의 숫자들을 이진탐색트리로 만들면 매우 쉽게 나온다.
3. 근데 숫자들을 보면 1, 2, 3, 4, 5, 6이 들어가 있는 위치가 중위순회를 했을 때 나오는 값이다.
4. 위의 이진탐색트리를 중위순회하면 1, 2, 3 ,4, 5, 6이 나온다. 이걸 이용한다.
5. 이를 트리의 값으로 저장하면 된다. 

 

---

풀이 및 해설

cnt = 1
def make_tree(v):
    global cnt
    if v > N:
        return
    # 왼쪽 자식의 인덱스는 현재 인덱스의 2배
    make_tree(v*2)
    # 현재 인덱스에 cnt를 저장
    tree[v] = cnt
    cnt += 1
    # 오른쪽 자식의 인덱스는 현재 인덱스의 2배 + 1
    make_tree(v*2+1)

for tc in range(int(input())):
    N = int(input())
    tree = [0] * (N+1)

    make_tree(1)
    print(f'#{tc+1} {tree[1]} {tree[N//2]}')
    cnt = 1