[백준/파이썬]20551번 Sort 마스터 배지훈의 후계자

-코드

from sys import stdin


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


n, m = map(int, stdin.readline().split())
array = sorted([int(stdin.readline()) for _ in range(n)])
for _ in range(m):
    d = int(stdin.readline())
    print(bin(0, n - 1, array, d))

처음에는 그냥 for문을 활용해서 했으나 시간 초과가 생겨서 분류를 보니 이분 탐색이어서 이분 탐색을 이용하여 풀었습니다. 

하지만 2번째 입출력인 중복된 수가 있을 경우에 문제가 생겨서 찾아보니 문제가 된 부분이 같은 수가 주어질 때 가장 처음의 위치를 출력해야하는 lower_bound라는 개념이 었습니다. 그래서 이 부분을 찾아보니 해결법이 end값이 mid값이랑 같아질 때, while문을 빠져나오게 하면 된다는 것을 알고 아닐 경우 end를 mid로 바꿔주면 target과 arr[mid]가 같은 가장 처음에 위치를 가리킬 때까지 end값에 mid가 들어가므로 해결이 되었습니다.

그리고 제가 나름대로 줄여보려고 d가 리스트에 포함이 되어있지 않을 경우 -1을 출력하게 따로 if문으로 빼고 그 외의 경우 함수에 들어가게 하였지만 not in 때문인지 시간 초과가 생기게 되어 함수 부분에 리스트 안에 값이 없을 경우 -1을 리턴하게 해서 해결을 하였습니다.