[ 자료구조-1920 ] 수 찾기(python)

1920 수 찾기

---

 

접근법

Array를 이용한 BST를 만들어서 접근하려고 했지만, 너무 과하고 시간이 문제여서 Binary Search를 유사하게 구현해서 접근하기로 하였다. 

---

정답

import sys
import math

N = int(input())

inputs = list(map(int,sys.stdin.readline().split(" ")))
inputs.sort()

M = int(input())
array = list(map(int,sys.stdin.readline().split(" ")))


for i in range(0,M):
    L = 0
    R = N-1 
    flag = False
    
    while L<=R:
        mid = math.ceil((L+R)/2)
        if( array[i] == inputs[mid]):
            flag = True
            break
        elif( array[i] > inputs[mid]):
            L = mid
            if(array[i] > inputs[R]):break
        else:
            R = mid-1
            if(array[i] < inputs[L]):break
            
    if flag:
        print("1")
    else: 
        print("0")

 

첫번째로 받아오는 inputs는 sort()를 사용하여 정렬시켰다.

 

L,R을 배열의 양 끝 index로 설정하고 L이 R보다 같거나 작을 때 까지 반복하도록 하였다. 

mid 즉, inputs list의 중앙값 계산 시 math.ceil()을 이용해 올림시켰다.

 

이때, L=R이여서 mid 값이 계속 같아져 무한 loop에 빠지는 경우를 방지하기 위해 비교할 값이 inputs[R]보다 크거나, inputs[L]보다 작은 경우를 예외처리 하였다.