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)