숫자로 이루어진 리스트 nums가 주어졌을 때, 연속된 숫자들의 부호가 양수와 음수로 번갈아 바뀌는 가장 긴 부분 수열(subsequence)의 길이를 구하는 프로그램을 만들어 보겠습니다.
문제 예시
예를 들어 입력이 다음과 같다고 가정해 봅시다.
nums = [1, 3, -6, 4, -3]
이 경우 출력은 4가 됩니다. [1, -6, 4, -3]처럼 양수와 음수가 교차하도록 원소를 선택할 수 있고, 이보다 더 긴 부호 교차 부분 수열은 존재하지 않기 때문입니다.
해결 접근 방법
이 문제는 동적 계획법(DP) 개념을 활용한 간단한 선형 탐색으로 해결할 수 있습니다. 핵심 아이디어는 두 개의 변수를 유지하는 것입니다.
- pos: 마지막 원소가 양수인 부호 교차 부분 수열 중 가장 긴 길이
- neg: 마지막 원소가 음수인 부호 교차 부분 수열 중 가장 긴 길이
리스트를 순회하면서 각 숫자의 부호에 따라 값을 갱신합니다. 현재 숫자가 음수라면, 직전까지 양수로 끝나는 최장 수열 뒤에 붙일 수 있으므로 neg = pos + 1이 됩니다. 반대로 현재 숫자가 양수(또는 0)라면 pos = neg + 1로 갱신합니다.
알고리즘 단계
- pos := 0, neg := 0으로 초기화합니다.
- nums의 각 원소 n에 대해 다음을 반복합니다.
- n < 0이면 neg := pos + 1
- 그렇지 않으면 pos := neg + 1
- pos와 neg 중 최댓값을 반환합니다.
Python 구현 코드
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
예제
class Solution: def solve(self, nums): pos = neg = 0 for n in nums: if n < 0: neg = pos + 1 else: pos = neg + 1 return max(pos, neg) ob = Solution() nums = [1, 3, -6, 4, -3] print(ob.solve(nums))
입력
[1, 3, -6, 4, -3]
출력
4
복잡도 분석
- 시간 복잡도: O(n) — 리스트를 한 번만 순회하면 됩니다.
- 공간 복잡도: O(1) — 두 개의 변수만 사용하므로 추가 메모리가 거의 필요하지 않습니다.
이 방식은 각 단계에서 이전 상태만 참조하기 때문에 매우 효율적이며, 리스트의 크기가 커져도 안정적으로 동작합니다.