[이진탐색] 떡볶이 떡 만들기 + map, 리스트 컴프리헨션

map 함수

map(함수, 데이터)

• 함수: 각 요소에 적용할 함수입니다. 일반적으로는 lambda 함수나 int와 같은 일반적인 함수가 사용됩니다.
• 데이터: 함수를 적용할 대상 데이터입니다. 이 데이터는 반복 가능한(iterable) 형태여야 합니다. 리스트, 튜플, 세트 등이 사용될 수 있습니다.

---

리스트 컴프리헨션(list comprehension)

리스트 컴프리헨션(list comprehension)은 파이썬에서 리스트를 생성하는 간결하고 효율적인 방법입니다.

[표현식 for 항목 in iterable if 조건]

• 표현식: 반복하는 동안 각 항목에 대한 계산이나 조작을 정의하는 표현식입니다. 이 표현식을 통해 나온 값이 리스트의 각 요소로 들어가게 됩니다.
• 항목: 반복 가능한(iterable) 객체에서 가져온 각 요소입니다. 
• iterable: 반복 가능한(iterable) 객체로, 리스트, 튜플, 세트, 문자열 등이 될 수 있습니다.
• 조건: 선택적으로 사용되며, 반복되는 항목을 필터링하는데 사용됩니다. 조건이 참인 경우에만 해당 항목이 결과 리스트에 포함됩니다.

예를 들어, 아래 코드는 

new_list = [x - 1 for x in original_list]

original_list의 각 요소에 1을 빼서 새로운 리스트 생성하는 코드입니다.

---

import time

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

start_time = time.time() # 측정 시작

# 아이디어 : 조건의 만족 여부에 따라 탐색범위를 좁혀 나간다. == 이진탐색

def binary_search(array, target, start, end):
  if start>end:
    return None
  
  mid = (start + end)//2 #몫

  # 잘린 떡의 길이 계산하기
  remain = sum(list(map(lambda x:x-array[mid] if x > array[mid] else 0, dduck)))
  
  # 찾은 경우
  if remain==target:
    print(mid)
    return mid
    
  # 중간점의 값보다 찾고자 하는 값이 작은 경우 -> 끝점 이동
  elif remain>target:
    print(mid)
    return binary_search(array, target, start, mid-1)
    
  # 중간점의 값보다 찾고자 하는 값이 큰 경우 -> 시작점 이동
  else:
    print(mid)
    return binary_search(array, target, mid+1, end)

result = binary_search(dduck, m, 0, len(dduck))

print(dduck[result])

end_time = time.time()
print("측정 시간 : ", end_time - start_time)

시간 제한 통과!

나동빈 씨 코드랑 좀 다른 거 같아서 고쳐봤다.

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

start = 0
end = max(dduck)
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
    start = mid + 1

print(result)

저는 재귀적인 이진탐색을 활용하고 나동빈 씨는 반복적인 이진탐색을 활용했습니다. 그리고 저는 인덱스를 통해 값을 계산했는데 나동빈 씨는 떡의 길이를 바로 계산하여 더 효율적이라고 생각됩니다.

효율적인 측면에서 제 코드가 아쉬운 부분이 크지만, 이번에 코드를 작성하며 파이썬 구문법과 map, lambda등을 확실히 알게 되어 좋습니다!

---

https://youtu.be/94RC-DsGMLo?feature=shared

강의 들으며 필기한 것!