문제 개요
비내림차순(오름차순)으로 정렬된 숫자 리스트 nums가 주어졌을 때, 이 리스트를 여러 개의 부분 수열로 분할할 수 있는지 확인하는 프로그램을 만들어 보겠습니다. 이때 각 부분 수열은 다음 조건을 만족해야 합니다.
- 각 부분 수열의 길이는 최소 3 이상이어야 합니다.
- 각 부분 수열은 1씩 연속적으로 증가하는 숫자(예: 4, 5, 6, 7)로 구성되어야 합니다.
예를 들어 입력이 nums = [2, 3, 4, 4, 5, 6, 7]이라면 결과는 True입니다. 이 리스트는 [2, 3, 4]와 [4, 5, 6, 7] 두 개의 부분 수열로 나눌 수 있기 때문입니다.
해결 접근 방법
이 문제는 각 숫자의 등장 횟수를 기준으로 부분 수열의 시작점과 끝점을 추적하여 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- counts : nums의 각 원소와 그 등장 횟수를 저장한 맵(Counter)을 만듭니다.
- starts : 각 부분 수열의 시작 값을 저장할 새 리스트를 만듭니다.
- ends : 각 부분 수열의 끝 값을 저장할 새 리스트를 만듭니다.
- 정렬된 순서대로 counts의 각 값 x에 대해 다음을 검사합니다.
- count[x] > count[x - 1]이면, x에서 시작해야 하는 부분 수열이 (count[x] - count[x - 1])개 존재하므로 해당 개수만큼 x를 starts에 추가합니다.
- count[x] > count[x + 1]이면, x에서 끝나야 하는 부분 수열이 (count[x] - count[x + 1])개 존재하므로 해당 개수만큼 x를 ends에 추가합니다.
- 모든 (start, end) 쌍이 start + 2 <= end 조건을 만족하면 True를 반환하고, 하나라도 만족하지 않으면 False를 반환합니다.
여기서 start + 2 <= end 조건은 각 부분 수열이 최소 3개의 연속된 숫자(start부터 end까지)를 포함해야 한다는 의미입니다.
Python 코드 예제
다음 구현을 통해 더 자세히 이해해 보겠습니다.
from collections import Counter class Solution: def solve(self, nums): count = Counter(nums) starts = [] ends = [] for x in sorted(count): if count[x] > count[x - 1]: starts.extend([x] * (count[x] - count[x - 1])) if count[x] > count[x + 1]: ends.extend([x] * (count[x] - count[x + 1])) return all(s + 2 <= e for s, e in zip(starts, ends)) ob = Solution() nums = [2, 3, 4, 4, 5, 6, 7] print(ob.solve(nums))
입력
[2, 3, 4, 4, 5, 6, 7]
출력
True
동작 원리 상세 설명
위 예제에서 각 숫자의 등장 횟수는 2: 1회, 3: 1회, 4: 2회, 5: 1회, 6: 1회, 7: 1회입니다. 알고리즘이 동작하는 과정은 다음과 같습니다.
- x = 2일 때 count[2](1) > count[1](0)이므로 starts에 2가 추가됩니다.
- x = 4일 때 count[4](2) > count[3](1)이므로 starts에 4가 추가됩니다.
- x = 4일 때 count[4](2) > count[5](1)이므로 ends에 4가 추가됩니다.
- x = 7일 때 count[7](1) > count[8](0)이므로 ends에 7이 추가됩니다.
결과적으로 starts = [2, 4], ends = [4, 7]이 되며, (2, 4)와 (4, 7) 쌍 모두 start + 2 <= end 조건을 충족하므로 최종적으로 True가 반환됩니다. 이 방식의 시간 복잡도는 O(n log n)으로, 리스트를 정렬된 순서로 한 번만 순회하면 되기 때문에 효율적입니다.