이코테 CHAPTER 07 이진 탐색 실전 문제

실전문제

부품 찾기

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다.

어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다.

동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다.

이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

 

• 나의 풀이

N = int(input())
all = list(map(int,input().split()))
M = int(input())
find = list(map(int,input().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 find:
    result = binary_search(sorted(all), i, 0, N - 1)
    if result == None:
    	print('no',end=' ')
    else:
	    print('yes',end=' ')

- 답안 예시 코드(이진 탐색)와 95% 일치한다.

- 이진 탐색이 아닌 방법으로 푸는 예시가 더 직관적인 것 같다.

 

• 답안 예시 코드(계수 정렬)

# 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=' ')

 

• 답안 예시 코드(집합 자료형 이용)

# N(가게의 부품 개수)을 입력받기
n = int(input())
# 가게에 있는 전체 부품 번호를 입력받아서 집합(set) 자료형에 기록
array = set(map(int, input().split()))

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

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
	# 해당 부품이 존재하는지 확인
	if i in array:
		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())
dduk = list(map(int,input().split()))

array = list(range(max(dduk)))

def binary_search(array, dduk, m, start, end):
    result = 0
    while start <= end:
        mid = (start + end) // 2
        total = sum([i-mid if i>mid else 0 for i in dduk])
        if total < m:
            end = mid - 1
        else:
            result = mid
            start = mid + 1
    return result

print(binary_search(array, dduk, m, 0, max(dduk)))

- 처음에는 풀이와 다르게 if 조건에서 '적어도'라는 조건을 생각하지 않고 기본적인 이진탐색 코드처럼 구현함

- 나의 풀이에서는 굳이 저장하지 않아도 되는 array를 추가로 저장함

- 함수 대신 바로 while문으로 구현하는게 더 간결함

 

• 답안 예시 코드

# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력받기
n, m = list(map(int, input().split()))
# 각 떡의 개별 높이 정보를 입력받기
array = list(map(int, input().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행(반복적)
resuIt = 0
while(start <= end):
    total = 0
    mid = (start + end) // 2
    for x in array: # 잘랐을 때의 떡의 양 계산
        if x > mid:
            total += x - mid
            
    # 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
    if total < m:
        end = mid - 1
    # 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
    else:
        result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
        start = mid + 1

# 정답 출력
print(result)

 

 

 

Reference

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저