파이썬으로 배열을 길이 K 이상의 증가 부분 수열로 나누는 방법

문제 개요

오름차순(비내림차순)으로 정렬된 양의 정수 배열 nums와 정수 K가 주어졌을 때, 이 배열을 길이가 각각 K 이상인 하나 이상의 서로 겹치지 않는 증가 부분 수열로 나눌 수 있는지 판별해야 합니다.

예를 들어 nums = [1,2,2,3,3,4,4], K = 3일 때 결과는 True입니다. 배열을 [1,2,3,4]와 [2,3,4]라는 두 부분 수열로 나눌 수 있으며, 각 수열의 길이가 모두 3 이상이기 때문입니다.

접근 방법

핵심은 각 숫자의 등장 빈도입니다. 배열이 정렬되어 있으므로 값이 같은 원소들은 동일한 증가 부분 수열에 함께 들어갈 수 없습니다. 따라서 필요한 부분 수열의 최소 개수는 '가장 자주 등장하는 값의 빈도'와 같습니다.

모든 부분 수열의 길이가 최소 K 이상이어야 하므로, 전체 원소 개수가 (최대 빈도 × K)보다 크거나 같으면 나누기가 가능하고, 그렇지 않으면 불가능합니다.

알고리즘 단계

1. 빈도를 저장할 딕셔너리 d를 생성하고 req를 0으로 초기화합니다.
2. nums의 각 원소 i에 대해 다음을 수행합니다.
   • i가 d에 없으면 d[i] = 1, 이미 있으면 d[i] += 1
   • req를 max(req, d[i])로 갱신합니다.
3. 반복이 끝나면 req * K <= len(nums) 여부를 반환합니다.

구현 코드

class Solution(object):
    def canDivideIntoSubsequences(self, nums, K):
        d = {}
        req = 0
        for i in nums:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
            req = max(req, d[i])
        return req * K <= len(nums)

ob = Solution()
print(ob.canDivideIntoSubsequences([1,2,2,3,3,4,4], 3))

입력

[1,2,2,3,3,4,4], 3

출력

True

Counter를 활용한 간결한 풀이

파이썬의 collections.Counter를 사용하면 같은 로직을 더 짧고 읽기 쉽게 작성할 수 있습니다.

from collections import Counter

def canDivideIntoSubsequences(nums, K):
    cnt = Counter(nums)
    return max(cnt.values()) * K <= len(nums)

복잡도 분석

• 시간 복잡도: O(n) — 배열을 한 번만 순회합니다.
• 공간 복잡도: O(n) — 최악의 경우(모든 원소가 고유할 때) 딕셔너리에 n개의 키가 저장됩니다.