숫자 리스트 logs와 값 limit이 주어져 있다고 가정해 보겠습니다. logs[i]의 각 요소는 i번째 사용자가 생성한 로그의 크기를 나타내고, limit은 데이터베이스에 저장할 수 있는 로그의 총 크기(용량 제한)를 의미합니다. 우리가 구해야 할 것은 가장 큰 값 x입니다. 즉, 모든 로그를 각각 최대 크기 x로 잘라냈을 때 남은 로그 크기의 합이 limit 이하가 되도록 하는 x입니다. 만약 어떤 로그도 잘라낼 필요가 없다면, 단순히 가장 큰 로그의 크기를 그대로 반환하면 됩니다.
예를 들어 입력이 logs = [500, 200, 10000, 500, 4000]이고 limit = 3000이라면 출력은 900입니다. 로그를 900으로 잘라내면 [500, 200, 900, 500, 900]이 되고, 이때 합계가 정확히 3000이 되어 저장 한도를 딱 맞춰 활용할 수 있기 때문입니다.
문제 해결 접근 방법
이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 잘라내는 기준 값 x가 커질수록 잘라낸 후의 로그 합계도 단조롭게 증가한다는 성질이 있기 때문에, 조건을 만족하는 x의 범위를 절반씩 좁혀 가며 최댓값을 빠르게 찾을 수 있습니다.
구체적인 풀이 단계는 다음과 같습니다.
- 탐색 하한 lo := 0으로 초기화합니다.
- 탐색 상한 hi := 1 + logs의 최댓값으로 설정합니다.
- lo + 1 < hi를 만족하는 동안 아래 과정을 반복합니다.
- 중간값 mi := lo + (hi - lo) // 2 를 계산합니다.
- 모든 로그를 min(mi, log)로 잘라낸 값들의 합이 limit 이하라면, 더 큰 값도 가능하므로 lo := mi로 갱신합니다.
- 그렇지 않다면 한도를 초과한 것이므로 hi := mi로 갱신합니다.
- 반복이 끝나면 lo를 반환합니다. 이것이 조건을 만족하는 최대 크기입니다.
예제 코드
아래 파이썬 구현을 통해 동작 방식을 더 쉽게 이해할 수 있습니다.
def solve(logs, limit):
lo, hi = 0, max(logs) + 1
while lo + 1 < hi:
mi = lo + (hi - lo) // 2
if sum(min(mi, log) for log in logs) <= limit:
lo = mi
else:
hi = mi
return lo
logs = [500, 200, 10000, 500, 4000]
limit = 3000
print(solve(logs, limit))입력
[500, 200, 10000, 500, 4000], 3000
출력
900
이 알고리즘의 시간 복잡도는 O(n log m)입니다. 여기서 n은 로그의 개수, m은 로그의 최댓값입니다. 매 반복마다 탐색 범위가 절반으로 줄어들고, 각 단계에서 전체 로그 합계를 O(n)으로 계산하기 때문입니다. 선형 탐색으로 모든 값을 하나씩 확인하는 방식보다 훨씬 효율적으로 최적의 잘라내기 크기를 구할 수 있습니다.