각 항목이 [시작(start), 끝(end)] 두 개의 값으로 구성된 상자 리스트가 있다고 가정해 봅시다(단, start < end). 한 상자의 끝값과 다른 상자의 시작값이 같다면 두 상자를 연결할 수 있습니다. 이때 우리가 구해야 할 것은 이렇게 연결하여 만들 수 있는 가장 긴 상자 체인의 길이입니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
blocks = [[4, 5], [5, 6], [4, 8], [1, 2], [2, 4]]
이 경우 출력은 4가 됩니다. [1, 2] → [2, 4] → [4, 5] → [5, 6] 순서로 체인을 형성할 수 있기 때문입니다.
문제 해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)의 아이디어를 활용하면 효율적으로 풀 수 있습니다. 각 끝값(end)을 기준으로 그 지점에서 끝나는 체인의 최대 길이를 저장하는 딕셔너리를 사용합니다. 알고리즘은 다음과 같습니다.
상자 리스트가 비어 있다면 0을 반환합니다.
상자 리스트를 정렬합니다. 정렬을 통해 체인을 순서대로 확장할 수 있습니다.
빈 맵(딕셔너리)을 하나 준비합니다.
각 상자의 시작값 s와 끝값 e에 대해 다음을 수행합니다.
dic[e] := max(dic[e], dic[s] + 1)
딕셔너리에 저장된 모든 값 중 최댓값을 반환합니다.
여기서 핵심은, 어떤 상자 [s, e]가 주어졌을 때 's에서 끝나는 체인의 길이 + 1'이 곧 'e에서 끝나는 체인의 후보 길이'가 된다는 점입니다. defaultdict(int)를 사용하면 아직 등장하지 않은 키도 기본값 0으로 처리되어 편리합니다.
구현 예제
import collections class Solution: def solve(self, boxes): if not boxes: return 0 boxes.sort() dic = collections.defaultdict(int) for s, e in boxes: dic[e] = max(dic[e], dic[s] + 1) return max(dic.values()) ob = Solution() boxes = [ [4, 5], [5, 6], [4, 8], [1, 2], [2, 4] ] print(ob.solve(boxes))
입력
[[4, 5], [5, 6], [4, 8], [1, 2], [2, 4]]
출력
4
동작 원리 살펴보기
위 코드가 실행되는 과정을 단계별로 보면 다음과 같습니다.
리스트를 정렬하면 [[1, 2], [2, 4], [4, 5], [4, 8], [5, 6]]이 됩니다.
[1, 2] 처리: dic[2] = max(dic[2], dic[1] + 1) = 1
[2, 4] 처리: dic[4] = max(dic[4], dic[2] + 1) = 2
[4, 5] 처리: dic[5] = max(dic[5], dic[4] + 1) = 3
[4, 8] 처리: dic[8] = max(dic[8], dic[4] + 1) = 3
[5, 6] 처리: dic[6] = max(dic[6], dic[5] + 1) = 4
딕셔너리 값들 {2: 1, 4: 2, 5: 3, 8: 3, 6: 4} 중 최댓값인 4가 최종 결과로 반환됩니다.
복잡도 분석
정렬에 O(n log n)의 시간이 소요되고, 이후 각 상자를 한 번씩 순회하므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 딕셔너리에 고유한 값들을 저장하므로 O(n)입니다.