Python에서 숫자 리스트가 유효한 그룹으로 나누어지는지 확인하는 프로그램

문제 소개

숫자로 구성된 리스트 nums가 주어졌을 때, 리스트의 모든 숫자를 아래 규칙 중 하나에 해당하는 그룹으로 나눌 수 있는지 확인하는 프로그램을 만들어 보겠습니다.

• 규칙 1: 연속된 두 개의 동일한 숫자 쌍 (a, a)
• 규칙 2: 연속된 세 개의 동일한 숫자 (a, a, a)
• 규칙 3: 연속된 세 개의 연속 숫자 (a, a+1, a+2)

예를 들어 입력이 nums = [7, 7, 3, 4, 5]라면 결과는 True입니다. [7, 7]은 규칙 1의 쌍으로 묶을 수 있고, [3, 4, 5]는 규칙 3의 연속된 세 숫자로 묶을 수 있기 때문입니다.

풀이 접근 방식

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 dp[i]를 "앞에서 i개의 숫자를 유효한 그룹들로 나눌 수 있는지"를 나타내는 값으로 정의하는 것입니다.

구체적인 단계는 다음과 같습니다.

1. n을 리스트 nums의 길이로 설정합니다.
2. 크기가 n+1인 DP 테이블 dp를 만들고, 첫 번째 값만 True, 나머지는 모두 False로 초기화합니다.
3. i를 2부터 n까지 반복하며 다음 조건을 검사합니다.
   • i ≥ 2이고 dp[i-2]가 참일 때, 마지막 두 원소 nums[i-1]과 nums[i-2]가 같다면 dp[i]를 True로 설정합니다. (쌍 그룹 형성)
   • i ≥ 3이고 dp[i-3]가 참일 때, 마지막 세 원소가 모두 같거나 서로 1씩 차이 나는 연속 숫자라면 dp[i]를 True로 설정합니다. (삼중 그룹 형성)
4. 최종적으로 dp[n]을 반환합니다. 이 값이 전체 리스트의 유효 여부를 나타냅니다.

Python 구현 예제

class Solution:
    def solve(self, nums):
        n = len(nums)
        dp = [True] + [False] * n
        for i in range(2, n + 1):
            if i >= 2 and dp[i - 2]:
                if nums[i - 1] == nums[i - 2]:
                    dp[i] = True
            if i >= 3 and dp[i - 3]:
                if (nums[i - 1] == nums[i - 2] == nums[i - 3]) or (nums[i - 1] == nums[i - 2] + 1 == nums[i - 3] + 2):
                    dp[i] = True
        return dp[n]
ob = Solution()
nums = [8, 8, 4, 5, 6]
print(ob.solve(nums))

실행 결과

입력:

[8, 8, 4, 5, 6]

출력:

True

위 예제에서 [8, 8]은 쌍 규칙으로, [4, 5, 6]은 연속된 세 숫자 규칙으로 각각 그룹화할 수 있으므로 결과는 True가 됩니다.

복잡도 분석

이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, DP 테이블 저장을 위한 공간 복잡도 역시 O(n)입니다. 덕분에 리스트의 길이가 커져도 선형 시간 안에 빠르게 판별할 수 있습니다.