[BaekJoon] 1920번 : 수 찾기 (Python)

코딩 1일 1문제! 오늘의 문제는 백준의 수 찾기 입니다.

1920번: 수 찾기

Solution

input_num = int(input())
numbers = list(map(int, input().split()))
numbers.sort()

input_num2 = int(input())
numbers2 = list(map(int, input().split()))

for num in numbers2:
    left, right = 0, len(numbers) - 1
    
    is_find = False
    
    while True:
        median = (left + right) // 2
        if num == numbers[median]:
            print(1)
            is_find = True
            break
        elif num > numbers[median]:
            left = median + 1
        elif num < numbers[median]:
            right = median - 1
            
        if left > right:
            break
            
    if not is_find:
        print(0)

Solution 풀이

먼저 몇개의 수를 입력받을 것인지 입력 받습니다.

그 다음 기준이 될 숫자들을 입력 받습니다.

그 다음 있는지 없는지 비교할 숫자를 몇 개 입력 받을 것인지 입력 받습니다.

그 다음 비교할 숫자를 입력받습니다.

 

이제 비교할 숫자 리스트에서 하나씩 꺼내서 numbers에 있는지 없는지 확인합니다.

in으로 확인해도 되지만 그렇게 하면 계속 O(n) 씩 걸리기 때문에

이분탐색으로 찾아야합니다.

 

비교할 숫자를 하나씩 꺼내옵니다.

먼저 left를 0 right를 numbers의 길이로 설정합니다.

 

그 다음 while 반복문을 돌아갑니다.

left와 right의 중간값을 구하고 이 중간값을 인덱스로 하여 numbers에서 가져온 값이

현재 하나씩 꺼내온 숫자와 같을 경우 1을 출력하고 is_find를 True로 바꾸고 반복문 종료

꺼내온 숫자가 더 클 경우에는 left의 값을 중간값 + 1로

꺼내온 숫자가 더 작을 경우에는 right의 값을 중간값 -1로 설정해줍니다.

 

만약! left 값이 right보다 클 경우!

반복문을 종료하고 0을 출력합니다.

https://github.com/SOMJANG/CODINGTEST_PRACTICE

SOMJANG/CODINGTEST_PRACTICE