[이코테]이진 탐색 문제 풀이(부품 찾기, 떡볶이 떡 만들기)

부품 찾기

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

 

내 답안(정답)

n = int(input())
list_n = list(map(int, input().split(' ')))
m = int(input())
list_m = list(map(int, input().split(' ')))

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

이는 집합 자료형을 이용한 풀이로

이 외에도 책에는 2가지 풀이가 더 소개되어 있다.

 

답안 예시

이진 탐색

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

n = int(input())
array = list(map(int, input().split()))
array.sort()   #이진 탐색을 수행하기 위해 사전에 정렬 수행

m = int(input())
x = list(map(int, input().split()))

#손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
    result = binary_search(array, i, 0, n-1)
    if result != None:
        print('yes', end = ' ')
    else:
        print('no', end = ' ')

 

계수 정렬

n = int(input())
array = [0] * 1000001

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

m = int(input())
x = list(map(int, input().split()))

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

---

떡볶이 떡 만들기

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.

절단이게 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.

예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다.

손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

 

답안 예시

n, m = map(int, input().split())
h = list(map(int, input().split()))

start = 0
end = max(h)

result = 0
while (start <= end):
    total = 0
    mid = (start+end)//2
    for x in h:
        if x > mid:   #떡의 길이가 더 길다면
            total += x - mid
    if total < m:
        end = mid - 1
    else:
        result = mid   #최대한 덜 잘랐을 때가 정답
        start = mid + 1

print(result)

4 6 

19 15 10 17

예시를 생각해보자.

 

시작점은 0, 끝점은 19, 중간점은 9이고 이때 떡의 합은 25이다.

result = 9

시작점을 증가시킨다.

 

시작점은 10, 끝점은 19, 중간점은 14이고 이때 떡의 합은 9이다.

result = 14

시작점을 증가시킨다.

 

시작점은 15, 끝점은 19, 중간점은 17이고 이때 떡의 합은 2이다.

끝점을 감소시킨다.

 

시작점은 15, 끝점은 16, 중간점은 15이고 이때 떡의 합은 6이다.

result = 15

시작점을 증가시킨다.

 

while문에서 시작점과 끝점이 16으로 동일하기 때문에 반복문을 탈출한다.

 

 

 

<출처>

이것이 취업을 위한 코딩테스트다 with 파이썬