1. 부품찾기
- 첫째 줄에 가게 부품 개수로 정수 N입력 (1<= N < 1,000,000)
- 둘째 줄에 공백으로 구분하여 N개의 부품 번호입력. 번호는 1보다 크고 1,000,000이하
- 셋째 줄에 손님이 요청한 부품 개수 정수 M입력 (1<= M <= 100,000)
- 넷째 줄에는 공백으로 구분하여 손님이 요청한 M개의 부품 번호 입력. 번호는 1보다 크고 1,000,000이해
출력 조건 : 첫째줄에 공백으로 구분하여 각 부품이 존재하면 'yes'를, 없으면 'no'를 출력.
1.1 내 답안
- 틀린 코드.
return없이 재귀함수만 호출했더니 오류남. in을 쓰는 것(집합 자료형 이용)만 생각했는데 이진탐색, 계수정렬도 이용가능!!
n = int(input())
input_data = list(map(int, input().split()))
m = int(input())
check = list(map(int, input().split()))
input_data = sorted(input_data)
def binary_search(array, start, end, target):
if start > end:
return None
mid = (start + end)//2
if array[mid]==target:
return True
elif array[mid] > target:
return binary_search(array, start, mid-1, target) # return없이 했더니 오류남.
else:
return binary_search(array, mid+1, end, target)
for i in range(m):
result = binary_search(input_data, 0, n-1, check[i])
if result != None:
print('yes', end=' ')
else:
print('no', end=' ')
1.2 책 답안(1)
- 이진탐색
def binary_search(array, start, end, target):
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())
input_data = list(map(int, input().split()))
input_data.sort()
m = int(input())
check = list(map(int, input().split()))
for i in check:
result = binary_search(input_data, 0, n-1, i)
if result != None:
print('yes', end=' ')
else:
print('no', end=' ')
1.3 책 답안(2)
- 계수 정렬
- array를 입력받고 for문으로 부품 번호 입력하는 과정을 간결하게
for i input().split():
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=' ')
1.4 책 답안(3)
- 집합 자료형 이용
- 이 문제는 집합자료형, 이진탐색, 계수정렬 모두 효과적인 방법
n = int(input())
input_data = set(map(int, input().split())) #집합자료형에 기록
m = int(input())
check = list(map(int, input().split()))
for i in check:
if i in input_data:
print('yes', end=' ')
else:
print('no', end= ' ')2. 떡볶이 떡 만들기
- 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M을 입력. (1<= N<= 1,000,000) (1<= M<= 2,000,000,000)
- 둘째 줄에 떡의 개별 높이가 주어짐. (떡 높이의 총 합은 항상 M 이상) (높이는 10억보다 작거나 같은 양의 정소 또는 0이다.
- 예) 길이가 [10, 15, 17, 19] 인 떡을 15길이로 자르면, 길이[0, 0, 2, 4]의 떡이 잘리고 총 길이는 6이다.
출력조건 : 적어도 길이 M만큼 떡을 가져가기 위해 절단기에 설정할 수 있는 높이 설정.
2.1 내 답안
- 소요시간 30분
- mid를 찾고 나서 적어도 길이 m 을 얻을 수 있는 높이의 최댓값 구하는 과정이 비효율적인 것 같음.
def binary_search(array, m, start, end):
# 정렬된 array
while start <= end:
mid = (start + end)//2
cut = sum(array[mid+1:])-array[mid]*mid # 잘린 떡 길이
if cut == m:
return mid
elif cut < m: # 떡 길이 부족, 높이 줄여야함
end = mid-1
else: # 떡 길이 넘침, 높이 늘려야함.
start = mid+1
return mid
n, m = map(int, input().split())
array = list(map(int, input().split()))
array.sort()
result = binary_search(array, m, 0, n-1)
for i in range(array[result-1],array[result+1]):
if sum([x-i for x in array if x >= i]) ==m :
print(i)
2.2 책 답안
- 절단기의 높이(탐색범위)가 1부터 10억까지의 정수 중 하나. 탐색범위가 크면 이진탐색을 떠올려야함.
- 나는 인덱스로 이진탐색했는데, 책에서는
0이상max(떡길이)이하 범위에서 이진탐색함.
- 떡 길이 array를 정렬할 필요가 없음! - 최대한 덜 잘랐을 때가 정답이므로
total>= m일 때 마다result = mid기록
n, m = map(int,input().split())
array = list(map(int, input().split()))
start = 0
end = max(array)
result = 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)
DEEP DIVER