[ALGORITHM] 7. 이진 탐색

이것이 취업을 위한 코딩테스트다 python 문제 풀이

7-5. 실전문제 '부품 찾기'

# C7. 이진 탐색 - 실전문제 '부품 찾기'

import sys
put = sys.stdin.readline

n = int(put())
store = list(map(int, put().split()))
m = int(put())
customer = list(map(int, put().split()))

for i in customer:
    if i in store:
        print("yes", end=' ')
    else: print("no", end=' ')

이진 탐색으로 풀기

# C7. 이진 탐색 - 실전문제 '부품 찾기' - 이진 탐색으로 풀기

import sys
put = sys.stdin.readline

n = int(put())
store = list(map(int, put().split()))
m = int(put())
customer = list(map(int, put().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 customer:
    result = binary_search(store, i, 0,  n-1)
    if result != None:
        print("yes", end=' ')
    else: print("no", end=' ')

책 풀이 - 계수 정렬

# N(가게의 부품 개수) 입력
n = int(input())
array = [0] * 1000001

# 가게에 있는 전체 부품 번호를 입력 받아서 기록
for i in input().split():
    array[int(i)] = 1

# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
    # 해당 부품이 존재하는지 확인
    if array[i] == 1:
        print('yes', end=' ')
    else:
        print('no', end=' ')

 

7-8. 실전문제 '떡볶이 떡 만들기'

# C7. 이진 탐색 - 실전문제 '떡볶이 떡 만들기'

import sys
put = sys.stdin.readline

n, m = list(map(int, put().split()))
heights = list(map(int, put().split()))

start = 0
end = max(heights)
answer = 0
while start <= end:
    total = 0
    mid = (start + end) // 2 
    #잘랐을 때의 총합
    for i in heights:
        if i > mid:
            total += i - mid    
    # 찾고자 하는 값(m)보다 총합이 적은 경우 왼쪽 확인
    if total < m:
        end = mid - 1
    # 찾고자 하는 값(m)보다 총합이 큰 경우 오른쪽 확인
    else:      
        answer = mid
        start = mid + 1

print(answer)