[이코테 - 이진탐색] 떡볶이 떡 만들기

 

• 문제 설명

첫 번째 줄에 떡의 개수 N과 떡의 길이 M이 주어지고 두 번째 줄에 떡들의 길이가 주어지면 이들을 각각 잘라서 M만큼 길이의 떡을 얻기 위한 절단기의 최댓값을 출력하면 된다.

 

• 문제 풀이

 

• 문제 코드

N, M = map(int,input().split())
lst = list(map(int,input().split()))

start = 0
end = max(lst)

result = 0
while start <= end:
    total = 0
    mid = (start + end) // 2
    for i in lst:
        if i > mid:
            total+=i-mid
    if total < M:
        end = mid - 1
    else:
        result = mid
        start = mid + 1
print(result)

 

이 문제는 이진 탐색을 생각해 내서 접근하기는 너무 어려운 문제였고 이진 탐색이라는 알고리즘을 알아도 적용하기 너무 어려워 책의 풀이를 참고하며 첨부하였다.

 

---

추가로 bisect에 대해서 알아보겠다.

 

• 문제 코드

from bisect import bisect_left,bisect_right
a = [1,2,9,4,5,2,3,6,2,7]
a.sort()
k = int(input())

def count_num(a,left,right):
    right_index = bisect_right(a,right)
    left_index = bisect_left(a,left)
    return right_index - left_index
print(count_num(a,k,k))

 

위 코드는 리스트에서 특정 숫자의 개수를 세기 위한 코드이며 k가 2일 때 3이 출력되는 것을 알 수 있다.

bisect모듈을 import한 후 bisect_left()와 bisect_right()를 사용할 수 있다.

 

1. 정렬된 배열에서 특정 사용할 수 있다 ---> 시간 복잡도 : O(logn)
2. bisect_left(a, x) : 정렬된 순서를 유지하면서 리스트 a에 x 삽입할 가장 왼쪽 인덱스 찾기
3. bisect_right(a,x) : 정렬된 순서를 유지하면서 리스트 a에 x 삽입할 가장 오른쪽 인덱스 찾기

-> 값이 특정 범위에 속하는 원소의 개수를 구하는데 사용할 수 있다!