[백준/BOJ] python 1920번 수 찾기

언어: python

번호: 1920

제목: 수 찾기

등급: 실버4

​

 

​

풀이 과정: 처음에는 for i in lst로 리스트 안에 있는지를 확인했더니 당연하게도 시간 초과가 떴다. 그래서 재귀문을 써서 풀려했다. n, lstn, m, lstm을 입력받아 숫자 리스트를 정렬하고 이진탐색으로. 가운데 값과 비교해서 작으면 왼쪽으로 가고, 크면 오른쪽으로 가려했다. 근데 잘 안됐다. 내 생각에 while문을 안 쓰고 length==0이라는 조건을 걸어서 탐색 횟수가 정해지니까 못 탐색하기 바로 전 단계에서 멈쳐버리는 것 같다. 이를 풀려면 변수를 하나 더 써서 while문에 조건을 걸어야할 것 같다. 

 

​

​

코드:

내가 잘못 푼 코드

#1920
n = int(input())
lstn = list(map(int, input().split()))
lstn = [0] + lstn
lstn.sort()

m = int(input())
lstm = list(map(int, input().split()))

def func(length, i, x):
    print(length, i, x, lstn[i])
    if lstn[i]==x:
        print(1)
        return
    else:
        if length==0:
            print(0)
            return
    
    if lstn[i]>x:
        func(length//2, i-length//2, x)
    elif lstn[i]<x:
        func(length//2, i+length//2, x)
    


for i in range(m):
    func(n//2, n//2, lstm[i])

 

인터넷에서 구글링한거

출처: https://tmdrl5779.tistory.com/115

n = int(input())
n_list = list(map(int, input().split(' ')))
n_list.sort()

m = int(input())
targets = list(map(int, input().split(' ')))


def binary(target):
    left = 0
    right = n - 1

    while left <= right:
        mid = (left + right) // 2
        if n_list[mid] == target:
            return True

        if target < n_list[mid]:
            right = mid-1
        elif target > n_list[mid]:
            left = mid + 1


for i in range(m):
    if binary(targets[i]):
        print(1)
    else:
        print(0)

 

 

 

메모:

다른 사람의 코드를 보는게 공부가 많이 된다고해서 열심히 뜯어봤다... 탐색 범위를 start~end로 잡고 가운데 비교하는 부분을 mid라 한다. 비교한 값에 따라 탐색 범위를 바꾸고 다시 탐색한다. 사전을 찾아보는것과 비슷하다. 나는 해당 문제를 풀때 재귀함수를 쓰다보니 자꾸 None값이 반환됐었는데 그냥 return 대신 print를 쓰면 됐었다...