이것이 취업을 위한 코딩테스트다 7회차 - 이진 탐색

이진 탐색

정렬된 배열에서 탐색 범위를 반씩 줄여가면서 탐색하는 방법

 

순차 탐색

배열에서 데이터를 앞에서부터 순서대로 탐색하는 방법

---

# 실전 문제 2. 부품 찾기
N = int(input())
arr = list(map(int, input().split()))
M = int(input())
target = list(map(int, input().split()))

def binary_search(target: int):
    st, en = 0, N-1
    while st <= en:
        mid = (st + en) // 2
        if arr[mid] < target:
            st = mid + 1
        elif arr[mid] > target:
            en = mid - 1
        else: # arr[mid] == target이면 존재
            return True
    return False # st와 en이 엇갈리게 되면, 존재하지 않음

arr.sort()
for item in target:
    if binary_search(item):
        print('yes', end = ' ')
    else:
        print('no', end = ' ')
print('\n')

 

# 실전 문제 3. 떡볶이 떡 만들기
N, M = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort() # 10 15 17 19

def get_height(height: int):
    sum = 0
    for x in arr:
        if x > height:
            sum += (x - height)
    return sum

st, en = 0, arr[N-1]
while st <= en:
    mid = (st + en) // 2
    if get_height(mid) < M:
        en = mid - 1
    else:
        res = mid    # 일단 기록해둬야함. 다음 반복때 st > en일수도 있기 때문.
        st = mid + 1    # 계속해서 더 큰 높이면서 조건을 만족하는 것이 있는지 탐색.

print(res)

bisect 라이브러리를 이용해서 풀 수도 있는 것 같으니, 해당 방법으로 푸는 법도 추가로 정리해야겠다.