[백준/Python] #1920 : 수 찾기 - 이분탐색

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

교재 실전문제 2번의 7-5번 풀이와 아주 유사한 문제 유형! 이어서 여유를 가지고 풀어봤

지만

ㅋ

?뭐가 틀린거임? 교재 코드 거의 똑같이 참고했구만

 

보니까

우선 15번째 줄에서 들여쓰기가 잘못됨. while문을 다 돌고 나와서 답을 찾을 수 없으면 그때 None을 반환하는게 맞음.

 

근데 이렇게 고치고 제출했더니 시간초과 뜨고

런타임 에러도 뜨고...

다른 사람들 풀이를 봐도 다 거의 이런식으로 풀었더만 왜 나만 통과 안시켜줘ㅠㅠ! 하고 있었는데

array를 sorting 시킨 부분의 위치가 문제였다.

import sys
input = sys.stdin.readline

N = int(input())
array = list(map(int, input().split()))
array.sort()
M = int(input())
check = list(map(int, input().split()))

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

for i in check:
    result = binary_search(array, i, 0, N - 1)
    if result != None:
        print(1)
    else:
        print(0)

처음에는 밑의 for문 안에서 binary_search() 호출할 때 sorted(array) 해줬어서 for문 돌 때마다 array를 정렬시켜준 뒤 인자로 넘겨줘야 해서 더 오래 걸렸던 것. 이렇게 고치니까 맨 위에서 한 번만 정렬시켜주면 된다.!

사실 이게 문제이려나? 싶어서 중간에 이렇게 수정해봤었는데, 괜히 다른 부분에서 시간 줄이겠다고 list를 set으로 바꾸고(set은 sort가 안됨 순서가 없어서..) 난리를 쳤더니 런타임 에러 뜬 거였음ㅎ

 

암튼 해결 !!