문제 개요
정수로 이루어진 두 개의 배열이 있다고 가정해 보겠습니다. 하나는 단위 폭을 가진 상자들의 높이 목록이고, 다른 하나는 창고(godown)를 이루는 각 방의 높이 목록입니다. 방은 0부터 n까지 번호가 매겨져 있으며, 각 방의 높이는 godown 배열의 해당 인덱스에 저장되어 있습니다. 이때 창고에 밀어 넣을 수 있는 상자의 개수를 구하는 것이 과제입니다.
단, 다음 세 가지 조건을 반드시 기억해야 합니다.
- 상자는 서로 위에 쌓을 수 없습니다.
- 상자를 넣는 순서는 자유롭게 변경할 수 있습니다.
- 상자는 왼쪽에서 오른쪽 방향으로만 넣을 수 있습니다.
만약 어떤 상자가 지나가야 할 방의 높이보다 크다면, 그 상자는 물론이고 그 오른쪽에 남은 모든 상자 역시 창고에 들어갈 수 없습니다.
입력 예시
예를 들어 boxes = [4, 5, 6], godown = [4, 5, 6, 7]이 주어졌다고 해 보겠습니다. 이 경우 출력은 1입니다. 첫 번째 방의 높이가 4이기 때문에 높이 4짜리 상자 하나만 들어갈 수 있고, 나머지 상자들은 반드시 첫 번째 방을 통과해야 하는데 그 방의 높이가 상자들보다 낮아 더 이상 넣을 수 없기 때문입니다.
해결 아이디어
이 문제의 핵심은 "어떤 상자가 k번째 방에 도달하려면 0번방부터 k번방까지 모두 통과할 수 있어야 한다"는 점입니다. 따라서 k번째 방의 실효 높이는 godown[0..k] 구간의 최솟값, 즉 누적 최솟값(prefix minimum)이 됩니다.
이를 활용하면 그리디 전략으로 문제를 풀 수 있습니다. 작은 상자부터 순서대로, 실효 높이가 큰 방부터 배치하면 전체적으로 가장 많은 상자를 넣을 수 있습니다.
알고리즘 단계
- boxes 리스트를 오름차순으로 정렬합니다.
- godown의 첫 번째 값으로 curmin 리스트를 초기화하고, cm에 그 값을 저장합니다.
- i를 1부터 godown의 길이 - 1까지 순회하며 다음을 수행합니다.
- cur := godown[i]
- cur < cm이면 cm := cur로 갱신합니다.
- cm을 curmin의 끝에 추가합니다. → curmin[j]는 j번째 방까지의 최소 높이를 의미합니다.
- 두 포인터 i := 0(상자 인덱스), j := godown 길이 - 1(방 인덱스), 결과 카운터 r := 0을 준비합니다.
- j >= 0이고 i < boxes 길이인 동안 반복합니다.
- curmin[j] >= boxes[i]이면 해당 상자를 이 방에 넣을 수 있으므로 i와 r을 각각 1씩 증가시킵니다.
- 매 반복마다 j를 1 감소시킵니다.
- 반복이 끝나면 r을 반환합니다. 이 값이 창고에 넣을 수 있는 상자의 최대 개수입니다.
Python 구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
def solve(boxes, godown):
boxes.sort()
curmin = [godown[0]]
cm = curmin[0]
for i in range(1, len(godown)):
cur = godown[i]
if cur < cm:
cm = cur
curmin.append(cm)
i, j = 0, len(godown) - 1
r = 0
while j >= 0 and i < len(boxes):
if curmin[j] >= boxes[i]:
i += 1
r += 1
j -= 1
return r
print(solve([4, 5, 6], [4, 5, 6, 7]))입력
[4, 5, 6], [4, 5, 6, 7]
출력
1
복잡도 분석
상자 정렬에 O(n log n), 누적 최솟값 계산과 매칭에 O(m)(m은 방의 개수)이 소요되므로 전체 시간 복잡도는 O(n log n + m)입니다. 공간 복잡도는 누적 최솟값 배열을 저장하기 위해 O(m)입니다.