Wiggle Subsequence

흔들 배열(wiggle subsequence)이란 배열에서 연속적인 수들 사이의 차이가 정확히 양수와 음수를 반복하는 배열을 뜻한다. 첫 번째 차이는 (만약 있다면) 양수든 음수든 다 가능하다. 하나의 원소만 있는 배열과 두 개의 서로 다른 원소를 갖는 배열은 따라서 모두 흔들 배열이다.

• 예를 들어, [1, 7, 4, 9, 2, 5] 배열은 흔들 배열이다. 원소의 차이가 [6, -3, 5, -7, 3]으로 양수와 음수를 반복하기 때문이다.
• [1, 4, 7, 2, 5]와 [1, 7, 4, 5, 5]는 흔들 배열이 아니다.

부분열(subsequence)은 배열에서 0개 이상의 원소를 삭제하고 나머지는 원래 순서 그대로 남겨서 얻을 수 있다.

정수 배열 nums가 주어졌을 때, 가장 긴 흔들 부분열의 길이를 구하자.

정수 배열의 크기는 1 ~ 1,000 사이이고 각 배열의 값은 0 ~ 1,000 사이이다.

탐욕 접근

정답이 부분배열(subarray)가 아니라 부분열(subsequence)라서, 탐욕적으로 접근해도 될 것 같다. 그러니까 처음부터 시작해서 흔들리는 조건을 만족하지 않으면 버리고, 만족하면 취하는 방식으로 해도 될 것 같다.

일단 자명한 케이스부터 걸러내자. 조건에 따라 길이가 1이면 곧바로 흔들 배열이다. 2인 경우에는 두 원소가 서로 다른 경우에만 흔들 배열이다. 3 이상의 배열에 대해서는, 일단 앞의 두 원소의 차이가 양수인지 음수인지에 따라서 달라진다. 우리는 (중간 원소를 버려서) 부분열을 취하여 가장 길이가 긴 것을 만들고 싶기 때문에, 흔들리는 조건을 체크할 때 맨 앞의 두 원소가 양수인지 음수인지 중요하다. 왜냐하면 맨 앞의 원소가 흔들리는 조건을 만족하면 이 두 원소는 길이가 가장 긴 부분열에 반드시 포함될 것이기 때문이다.

아무튼 자명한 케이스를 걸러내고 맨 앞의 두 원소가 음수인지 양수인지를 알면, 그 이후는 모든 원소를 다 돌면서 이 조건을 계속 만족한다면 취하고, 그렇지 않으면 거르면 된다.

def wiggleMaxLength(nums):
    if len(nums) < 2:
        return len(nums)
    prev = nums[1] - nums[0]
    maxlen = 1 if prev == 0 else 2
    for i in range(2, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and prev <= 0) or (diff < 0 and prev >= 0):
            maxlen += 1
            prev = diff
    return maxlen

• 처음에 prev가 0이면 맨 앞의 두 원소가 같다는 의미이므로 이때의 초기값은 1이다. 즉, 원소가 같은 부분은 다 퉁쳐서 하나의 원소가 되는 것이다.
• 비슷하게, 지금 확인 중인 차이(diff)가 음수 또는 양수라면 이전 차이(prev)는 엄밀하게 음수 또는 양수가 아니라 0이어도 된다. 예를 들어 [3, 3, 3, 3, 1] 에서 i = 4에서 diff < 0이지만 prev = 0이므로 무시되었던 부분(= 다 같은 부분 배열)을 하나의 원소(=마지막 원소)로 취급하여 올바른 계산을 하게 된다.