이진탐색 Python(SW Expert Academy)

전에 올린 게시글과 중복이 아닙니다.

문제 이름이 똑같은거입니다.

이전 게시글(Advanced의 이진탐색)

현재 게시글(Intermediate의 이진탐색)

 

난이도 : D2

문제번호 : 5176

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ-_6qfsDFAWg#

SW Expert Academy

---

 

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

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

---

2. 문제풀이

N이 주어지면 트리를 만든다음에 루트노드와 N/2번 노드를 출력하면 된다. 그렇다면 트리를 만들 줄 알아야 한다. 트리를 만드는 방식은 여러개가 있을 수 있지만 여기의 경우는 크기가 고정되어 있다. 추가적인 노드 삽입이나, 삭제가 없으므로 편하게 리스트를 이용하여 구현하였다. 부모노드는 왼쪽 자식노드보다 커야하고 오른쪽 자식노드보다는 작아야 한다. 그렇다면 제일 왼쪽부터 서브트리를 하나씩 돌면서 값을 넣어주면 된다. 제일 왼쪽 노드를 들어가기 위해 가장 편한방법으로 재귀함수를 이용했다. 왼쪽 자식 노드는 현재 노드의 *2 의 위치에 있다. 오른쪽 자식 노드는 현재 노도의 *2 +1 의 위치에 있다. 값은 왼쪽 < 자신 < 오른쪽 순이므로 왼쪽노드 타고 자기한테 값넣고 오른쪽 노드를 타는 방식으로 처리한다. 물론 범위체크는 필수이다.

---

3. 소스코드

 

#D2 5176 이진탐색
 
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]))