[파이썬] 5176. 이진탐색

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


1부터 N까지의 자연수를 이진 탐색 트리에 저장하려고 한다.

이진 탐색 트리는 어떤 경우에도 저장된 값이 왼쪽 서브트리의 루트 <현재 노드 <오른쪽 서브 트리의 루트인 규칙을 만족한다.

추가나 삭제가 없는 경우에는, 완전 이진 트리가 되도록 만들면 효율적인 이진 탐색 트리를 만들수 있다.

다음은 1부터 6까지의 숫자를 완전 이진 트리 형태인 이진 탐색 트리에 저장한 경우이다.

 
완전 이진 트리의 노드 번호는 루트를 1번으로 하고 아래로 내려가면서 왼쪽에서 오른쪽 순으로 증가한다.

N이 주어졌을 때 완전 이진 트리로 만든 이진 탐색 트리의 루트에 저장된 값과, N/2번 노드(N이 홀수인 경우 소수점 버림)에 저장된 값을 출력하는 프로그램을 만드시오.


[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 N이 주어진다. 1<=N<=1000

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

입력	출력
3 6 8 15	#1 4 6 #2 5 2 #3 8 14

 

🎁 다른사람 풀이

 

def makeTree(n):
  global count
  # 배열이니까 배열크기 넘어가지 않도록
  if n <= N :
    # 왼쪽 노드는 현재 인덱스의 2배
    makeTree(n*2)
    # 더이상 못가면 값넣기
    tree[n]=count
    # 값 넣었으면 증가시키기
    count+=1
    # 우측 노드는 인덱스 2배+1
    makeTree(n*2+1)

for t in range(int(input())):
  N=int(input())
  tree=[0 for i in range(N+1)]
  count=1
  makeTree(1)
  print('#{} {} {}'.format(t+1, tree[1], tree[N//2]))

 

1번부터 N번까지 리스트 tree를 만든다(0은 있어도 안씀).

시작 인덱스 1을 넣고 makeTree호출

n이 N보다 작거나 같을 동안에 리스트 tree에 값을 넣는다(1부터 N까지 값을 넣는다).

왼쪽, 오른쪽 각각 끝까지 들어갔다가 더이상 못내려가면 그 자리에 값을 넣는다.

 

class Tree:
  def __init__(self, N):
    self.lst=[0]*(N+1)
    self.N=N
    self.cnt=1
    self.numbering(1)

  def numbering(self, num):
    if num <= N :
      self.numbering(num*2)
      self.lst[num]=self.cnt
      self.cnt+=1
      self.numbering(num*2+1)

  def my_result(self):
    return ' '.join(map(str, (self.lst[1], self.lst[self.N//2])))

T=int(input())
for test_case in range(1, T+1):
  N=int(input())
  tree=Tree(N)
  print("#{} {}".format(test_case, tree.my_result()))

 

위와 같은 알고리즘.

 

# 재귀로 표현
def checkchild(start) :
  global N
  if start*2 <= N :
    array[start][1] = start*2
    checkchild(start*2)
  if start*2+1 <= N :
    array[start][2]=start*2+1
    checkchild(start*2+1)

# 시작점은 1번 노드
def inorder(start):
  global n
  if start :  
    inorder(array[start][1])
    array[start][0]=n
    n+=1
    inorder(array[start][2])

# 코드 구현
T=int(input())
for tc in range(T):
  N=int(input())

  array=[[0 for _ in range(3)] for __ in range(N+1) ] # 내 값, 왼쪽 자식, 오른쪽 자식
  checkchild(1)   # 1번부터 자식 있는 것까지 다 표시

  n=1
  inorder(1)

  # 결과 출력
  print("#%d" %(tc+1), array[1][0], array[N//2][0])

 

첫번째 테스트 케이스의 총 array가 [[0, 0, 0], [4, 2, 3], [2, 4, 5], [6, 6, 0], [1, 0, 0], [3, 0, 0], [5, 0, 0]] 나온다. 

4는 왼쪽이 2, 오른쪽이 6인데 안 맞는다;;

그리고 이 문제는 왼쪽 자식, 오른쪽 자식을 구할 필요가 없다.