[파이썬] 백준 1920 - 수 찾기

요즘 포스팅이 뜸했던 이유는, 막학기에 듣는 과목이 팀플과목이라 팀플에 집중하기도 했고, 요즘은 '깃허브'를 시작하게 되었다. (현업에 가면 깃허브를 많이 쓴다고해서 지금부터라도 손에 익히려고..ㅎ) 아무튼 알고리즘 공부했던 코드들을 깃허브에 commit과 push를 하고 있다.  오랜만에 새로운 문제를 풀면서 설명을 붙혀가며 포스팅하고 싶어, 이 블로그에다가 포스팅하려고 한다! (물론, 깃허브와 블로그 포스팅도 꾸준히 할 것이다!!)

'Binay Search' 즉, 이분탐색 알고리즘을 사용하여 푸는 문제이다.

<나의코드>

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
M_list = map(int, sys.stdin.readline().split())
A.sort()


def binarySearch(k, A, left, right):
    if left > right:
        return 0
    mid = (left+right)//2
    if k == A[mid]:
        return 1
    elif k < A[mid]:
        right = mid - 1
    else:
        left = mid + 1
    return binarySearch(k, A, left, right)


for k in M_list:
    left = 0
    right = len(A)-1
    print(binarySearch(k, A, left, right))

 

<시행착오>

k값의 위치, 중간값의 위치에 따라 left, right 값을 설정하는 것이 혼동되었음.

 

< 해결방안 >

중간값이 k 보다 작으면 왼쪽편에는 k값이 없으니 left 값을 mid + 1로 하여 오른편으로 이동시키고, 중간값이 k값보다 크면 k값이 없으니 right를 mid-1로 하여 왼쪽으로 이동시킨다는 개념을 확실히 숙지하고 문제를 풀었다.

 

 

✭ 블로그 포스팅, 깃허브 열심히하자!