문제
You are given a 0-indexed integer array books of length n where books[i] denotes the number of books on the ith shelf of a bookshelf.
You are going to take books from a contiguous section of the bookshelf spanning from l to r where 0 <= l <= r < n. For each index i in the range l <= i < r, you must take strictly fewer books from shelf i than shelf i + 1.
Return the maximum number of books you can take from the bookshelf.0부터 시작하는 인덱스를 사용하는 길이 n의 정수 배열 books가 주어집니다.
books[i]는 책장의 i번째 선반에 있는 책의 수를 나타냅니다.
당신은 책장에서 l부터 r까지의 연속된 구간을 선택하여 책을 가져가려고 합니다.
이때 0 <= l <= r < n을 만족해야 합니다.
선택한 구간에서 모든 l <= i < r에 대해,
i번째 선반에서 가져가는 책의 수는 반드시 i + 1번째 선반에서 가져가는 책의 수보다 엄격하게 적어야 합니다.
책장에서 가져갈 수 있는 책의 최대 개수를 반환하세요.
예시
입력: books = [8,5,2,7,9]
출력: 19
설명:
- 1번 선반에서 책 1권을 가져갑니다.
- 2번 선반에서 책 2권을 가져갑니다.
- 3번 선반에서 책 7권을 가져갑니다.
- 4번 선반에서 책 9권을 가져갑니다.
총 19권의 책을 가져갔으므로 19를 반환합니다.
19권이 가져갈 수 있는 책의 최대 개수임을 증명할 수 있습니다.
제한
풀이
class Solution:
def maximumBooks(self, books: List[int]) -> int:
def triangle(n: int) -> int:
if n <= 0:
return 0
return (n ** 2 + n) // 2
def area(end: int, size: int) -> int:
return triangle(end) - triangle(end - size)
N = len(books)
stack = []
dp = [0] * N
for i, v in enumerate(books):
while stack and books[stack[-1]] - stack[-1] >= v - i:
stack.pop()
if stack:
dp[i] = dp[stack[-1]] + area(v, i - stack[-1])
else:
dp[i] = area(v, i + 1)
stack.append(i)
return max(dp)1. 오른쪽 끝을 고정해서 생각하기
dp[i]를 다음과 같이 정의한다.
dp[i]=i번째 선반을 선택한 구간의 오른쪽 끝으로 했을 때 가져갈 수 있는 책의 최대 개수
오른쪽 끝 i에서 books[i]권을 가져간다고 생각해보자.
문제에서는 왼쪽 선반에서 가져가는 책의 수가 오른쪽 선반보다 반드시 작아야 한다.
따라서 최대한 많은 책을 가져가려면 왼쪽으로 갈수록
..., books[i] - 3, books[i] - 2, books[i] - 1, books[i]처럼 정확히 1씩 감소시키는 것이 최선이다.
예를 들어
books = [1, 8, 9, 6]에서 마지막 6을 기준으로 모든 선반을 사용한다면 이상적인 형태는
3, 4, 5, 6이다.
하지만 첫 번째 선반에는 책이 1권밖에 없으므로 실제로는
1, 4, 5, 6을 가져가게 된다.
즉 문제의 핵심은
오른쪽에서 시작한 **
1씩 감소하는 수열**을 어디까지 왼쪽으로 이어갈 수 있는가?
를 찾는 것이다.
2. 어떤 선반에서 수열이 끊기는가?
현재 오른쪽 끝을 j라고 하자.
j에서 books[j]권을 가져간다면, 왼쪽의 i번째 위치에서 가져가고 싶은 책의 수는
books[j] - (j - i)이다.
따라서 i번째 선반에 그만큼의 책이 존재하려면
books[i] >= books[j] - (j - i)여야 한다.
식을 정리하면
books[i] - i >= books[j] - j가 된다.
즉 각 위치에 대해
books[i] - i라는 값을 생각하면 된다.
현재 j보다 왼쪽에 있는 선반 중
books[i] - i >= books[j] - j인 위치들은 j에서 시작한 1씩 감소하는 수열을 그대로 적용할 수 있다.
반대로 처음으로
books[i] - i < books[j] - j인 위치를 만나면 그 선반은 필요한 책의 수보다 실제 책의 수가 적다.
따라서 그 위치에서 수열이 끊긴다.
3. 끊긴 이전 부분은 이미 계산해둔 값을 사용한다
j의 왼쪽에서 가장 가까운
books[i] - i < books[j] - j를 만족하는 위치가 i라고 하자.
그러면 구간을 두 부분으로 나눌 수 있다.
[ ... i ] [ i+1 ........ j ]
↑ ↑
이미 계산됨 1씩 증가하는 수열i + 1 ~ j 구간은 오른쪽의 books[j]에서 시작해 왼쪽으로 1씩 감소하는 형태가 된다.
그리고 i까지의 최적 결과는 이미 dp[i]에 저장되어 있다.
따라서
dp[j] = dp[i] + area(books[j], j - i)로 계산할 수 있다.
예를 들어
books = [1, 8, 9, 6]에서 마지막 6을 처리한다고 해보자.
마지막 위치에서 왼쪽으로 만들고 싶은 수열은
3, 4, 5, 6이다.
첫 번째 선반의 1은 필요한 3보다 작기 때문에 여기서 수열이 끊긴다.
따라서
[1] + [4, 5, 6]으로 나누어 생각할 수 있고,
앞의 [1]은 이미 계산된 dp[0],
뒤의 [4, 5, 6]은 등차수열의 합으로 계산하면 된다.
4. 등차수열의 합 계산
매번 실제로
4 + 5 + 6처럼 더하면 비효율적이므로 삼각수 공식을 이용한다.
def triangle(n: int) -> int:
if n <= 0:
return 0
return (n ** 2 + n) // 21 ~ n의 합은
n(n + 1) / 2이므로, 마지막 값이 end이고 길이가 size인 연속된 수열의 합은
triangle(end) - triangle(end - size)로 구할 수 있다.
예를 들어
4 + 5 + 6은
(1 + 2 + 3 + 4 + 5 + 6)
- (1 + 2 + 3)과 동일하다.
따라서 이를 area()로 계산한다.
def area(end: int, size: int) -> int:
return triangle(end) - triangle(end - size)또한 왼쪽으로 진행하다 값이 0 이하가 되는 경우에는 책을 더 가져갈 수 없으므로 triangle(n)에서 n <= 0을 0으로 처리한다.
5. 경계 위치를 빠르게 찾기
이제 필요한 것은 현재 j에 대해 가장 가까운 왼쪽 위치 i 중
books[i] - i < books[j] - j를 만족하는 위치를 찾는 것이다.
이를 매번 왼쪽으로 탐색하면 최악의 경우 O(N²)이 된다.
여기서 모노토닉 스택을 사용한다.
스택에는 books[i] - i 값이 엄격하게 증가하도록 인덱스를 유지한다.
현재 값보다 크거나 같은 값은 앞으로 현재 위치 때문에 경계점으로 사용될 일이 없으므로 제거한다.
while stack and books[stack[-1]] - stack[-1] >= books[i] - i:
stack.pop()이 과정이 끝난 뒤 스택의 top은
books[k] - k < books[i] - i를 만족하는 가장 가까운 왼쪽 위치가 된다.
따라서 스택이 비어 있지 않다면
dp[i] = dp[stack[-1]] + area(
books[i],
i - stack[-1]
)로 계산한다.
스택이 비어 있다면 중간에 수열을 끊는 선반이 없다는 의미이므로 처음부터 i까지 하나의 수열로 계산할 수 있다.
dp[i] = area(books[i], i + 1)마지막으로 현재 인덱스를 스택에 추가한다.
stack.append(i)6. 시간복잡도
각 인덱스는 모노토닉 스택에 정확히 한 번 들어가고 최대 한 번 제거된다.
따라서 스택에서 수행되는 전체 연산 횟수는 O(N)이다.
dp 계산과 등차수열 합 계산은 각각 O(1)이므로
시간복잡도: O(N)
공간복잡도: O(N)이 된다.
핵심을 정리하면 다음과 같다.
오른쪽 끝의 책을 모두 가져간다고 가정하면, 왼쪽으로 가져갈 수 있는 책의 수는 1씩 감소하는 형태가 된다.
books[i] - i를 이용하면 이 수열을 더 이상 이어갈 수 없는 경계점을 표현할 수 있고, 그 경계점을 모노토닉 스택으로 O(N)에 찾는다.경계 이전은 이미 계산한
dp를 재사용하고, 경계 이후는 등차수열의 합으로 O(1)에 계산한다.
