[파이썬/Python] 백준 2805번 나무 자르기

[파이썬/Python] 백준 2805번 나무 자르기

2805번: 나무 자르기

---

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

예제 입력 1

4 7
20 15 10 17

예제 출력 1

15

예제 입력 2

5 20
4 42 40 26 46

예제 출력 2

36

풀이 1

이진탐색

import sys

# 입력
n, m = map(int, sys.stdin.readline().split())
lst = list(map(int, sys.stdin.readline().split()))

start, end = 1, max(lst)  # 초기 시작과 끝 값 설정

while start <= end:
    sum = 0
    mid = (start + end) // 2  # 중간값 설정

    for l in lst:
        if l > mid:
            sum += l - mid  # 중간값을 기준으로 잘랐을 때 가져갈 수 있는 나무 길이 합 계산
    
    if sum < m:  # 가져갈 수 있는 나무 길이 합이 목표보다 작은 경우
        end = mid - 1  # 높이를 낮춰야 함
    else:  # 가져갈 수 있는 나무 길이 합이 목표보다 크거나 같은 경우
        start = mid + 1  # 높이를 높여야 함

print(end)  # 결과 출력

주어진 코드에서 최댓값을 end로 출력하는 이유는 이진 탐색 알고리즘의 특성 때문이다. 이진 탐색에서 start와 end는 탐색 범위를 좁혀가는 두 개의 포인터 역할을 한다. 탐색을 진행하면서 start와 end가 좁혀지고, 최종적으로 하나의 값에 수렴하게 된다.

이 문제에서는 절단기에 설정할 수 있는 높이의 최댓값을 구하는 것이 목표이다. 따라서, start와 end를 이진 탐색을 통해 좁혀갈 때, 최종적으로 end가 가리키는 값이 절단기에 설정할 수 있는 높이의 최댓값이 된다.

이진 탐색의 원리상 start와 end가 수렴하게 되는데, 최종적으로 start와 end가 같은 값을 가리키게 된다. 그러나 start와 end를 설정할 때 (start + end) // 2 연산을 수행하므로, 가운데 값을 구하는 것이 아니라 더 작은 값인 start를 사용하여 연산을 진행한다. 따라서, 최종적으로 start와 end가 같은 값이 되면 그 값이 최댓값이 아니라 최댓값보다 1 작은 값이 된다.

그래서 이진 탐색의 반복문이 끝나고 난 후에는 end를 출력하는 것이 맞다. end 값은 최종적으로 절단기에 설정할 수 있는 높이의 최댓값이 된다. 따라서, 주어진 코드에서는 end를 출력하는 것이 올바른 방식이다.

위의 코드의 시간 복잡도는 O(N log H)이다. 여기서 N은 나무의 수이고, H는 나무의 최대 높이다.

이진 탐색을 사용하여 절단기에 설정할 수 있는 높이의 최댓값을 찾는 과정에서 while 반복문이 실행된다. 이진 탐색은 매 반복마다 탐색 범위를 절반으로 줄여가는 특성을 가지므로, 반복 횟수는 log H에 비례한다. 여기서 H는 나무의 최대 높이다.

각 반복에서는 나무의 높이를 확인하고, 중간값을 기준으로 나무를 잘랐을 때 가져갈 수 있는 나무의 길이 합을 계산한다. 이 과정에서 모든 나무를 확인해야 하므로 시간 복잡도는 O(N)이다.

따라서, 전체 시간 복잡도는 O(N log H)가 된다. 이는 입력 크기에 비례하여 증가하는 시간 복잡도이며, 주어진 제한 범위에서 효율적으로 문제를 해결할 수 있다.

풀이 2

이진 탐색, Counter

import sys
from collections import Counter

# 입력
n, m = map(int, sys.stdin.readline().split())
trees = Counter(map(int, sys.stdin.read().split()))

# 초기 설정
s = 1
e = 1000000000

while s <= e:
    mid = (s + e) // 2  # 중간값 설정
    # 중간값을 기준으로 잘랐을 때 가져갈 수 있는 나무 길이 합 계산
    tot = sum((h - mid) * i for h, i in trees.items() if h > mid)

    if tot >= m:  # 가져갈 수 있는 나무 길이 합이 목표보다 크거나 같은 경우
        s = mid + 1  # 높이를 높여야 함
    elif tot < m:  # 가져갈 수 있는 나무 길이 합이 목표보다 작은 경우
        e = mid - 1  # 높이를 낮춰야 함

print(e)  # 결과 출력

앞선 코드와의 차이점에 대해서만 설명하겠다.
trees에 나무의 높이를 Counter 객체로 저장한다. Counter는 리스트나 이터러블 객체에서 각 원소의 개수를 세어 딕셔너리 형태로 반환하는 기능을 가지고 있다.

s와 e를 이용하여 이진 탐색을 진행한다. 중간값인 mid를 설정하고, 중간값을 기준으로 나무를 잘랐을 때 가져갈 수 있는 나무의 길이 합인 tot을 계산한다. 이 때, Counter 객체인 trees를 활용하여 중간값보다 높은 높이의 나무들에 대해서만 계산한다.

이진 탐색을 수행하는 동안 s와 e가 수렴하므로, 이진 탐색 반복 횟수는 O(log H)이다. tot을 계산하는 과정에서는 모든 나무를 확인해야 하므로, 나무의 수 N에 비례하는 시간이 소요됩니다. 따라서, 전체 시간 복잡도는 O(N log H)이다.

이전 코드의 실행 시간은 4772ms이고, 396ms 이다. 시간 복잡도는 같은데 큰 차이가 발생하는 이유는 무엇일까.

Counter 사용 유무가 실행 시간에 영향을 줄 수 있다.

Counter는 데이터의 빈도수를 세는 기능을 가지고 있으며, 내부적으로 해시 테이블을 사용하여 빠른 접근과 카운팅을 수행한다. Counter를 사용하면 나무의 높이를 저장하고 해당 높이의 개수를 세는 과정을 간단하게 구현할 수 있다.

반면에 Counter를 사용하지 않고 리스트를 직접 활용하는 경우, 나무의 높이를 저장하고 개수를 세기 위해 추가적인 로직과 반복문을 구현해야 한다. 이는 코드의 길이를 늘리고, 실행 시간을 더 소요할 수 있다.

따라서, Counter를 사용하여 데이터를 처리하는 것이 더 효율적일 수 있으며, 실행 시간을 단축시킬 수 있다. 하지만 이는 Counter를 사용하는 코드와 사용하지 않는 코드의 차이로 인한 것이며, 알고리즘의 본질적인 차이는 아니다. 알고리즘의 핵심은 이진 탐색에 기반한 부분이며, Counter 사용 여부는 세부 구현에 해당한다

 

참고자료

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

로그인

글 읽기 - 정답인데 과정 중 하나가 궁금합니다