숫자로 이루어진 리스트 nums와 값 k가 주어졌을 때, 이 리스트를 각 하위 리스트의 길이가 k 이상이면서 원소가 엄격하게 증가하는 여러 하위 리스트로 나눌 수 있는지 판별해야 합니다. 단, 하위 리스트가 반드시 연속된 구간일 필요는 없습니다.
예를 들어 입력이 nums = [6, 7, 5, 10, 13], k = 2라면 결과는 True입니다. 리스트를 [5, 6]과 [7, 10, 13]으로 나누면 두 하위 리스트 모두 길이가 2 이상이면서 엄격하게 증가하기 때문입니다.
접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- c := nums의 각 원소와 그 등장 횟수를 저장한 맵(Counter)
- max_count := c에 기록된 빈도수 중 최댓값
- max_count * k <= len(nums)이면 True를 반환하고, 그렇지 않으면 False를 반환
왜 이 조건이 성립할까요? 하위 리스트는 엄격하게 증가해야 하므로 하나의 하위 리스트에 같은 값이 두 번 이상 들어갈 수 없습니다. 따라서 가장 많이 등장한 값(max_count번 등장)은 반드시 서로 다른 max_count개의 하위 리스트에 배치되어야 합니다. 그리고 각 하위 리스트는 길이가 k 이상이어야 하므로, 전체 리스트의 길이는 최소 max_count × k 이상이어야만 분할이 가능합니다.
예제 코드 (Python)
다음 구현을 보면 더 쉽게 이해할 수 있습니다.
from collections import Counter class Solution: def solve(self, nums, k): c = Counter(nums) max_count = max(c.values()) return max_count * k <= len(nums) ob = Solution() nums = [6, 7, 5, 10, 13] k = 2 print(ob.solve(nums, k))
참고: 원본 코드에서는 리스트 컴프리헨션의 루프 변수 이름이 매개변수 k와 겹쳐 혼동을 일으킬 수 있었습니다. 위 코드에서는 c.values()를 사용해 이 문제를 피하고 가독성을 높였습니다.
입력
[6, 7, 5, 10, 13], 2
출력
True