[Leet Code] Wiggle Subsequence (Kotlin)

https://leetcode.com/problems/wiggle-subsequence/

Wiggle Subsequence - LeetCode

유형

DP or Greedy

과정

난이도가 medium 이었지만, 나 한정 hard였다. 신기하게도 어제는 아무리 문제를 뜯어보고 풀이를 맛봐도 알송달송했는데, 오늘은 이해가 된다.(쓰면서 알았다. 제대로 이해하진 못했다) 무의식에서 내 머리가 열심히 고생해준 것 같다ㅎ

 

처음 봤을 때 DP 같다는 생각이 들었다. 길이가 k인 배열에서 nums[k]를 지우냐, 지우지 않느냐에 따라서 가장 긴 wiggle sequence를 결정할 수 있을 것 같았다. 그래서 경우의 수를 따져보려고 했는데, 뭔가 복잡했다. 노트가 없었어서(^^;) 머리에서만 해결해려다 보니 그랬던 것 같다.

 

잘 모르겠어서 discussion을 찾아봤다. 리트 코드는 세계적으로 많은 유저들이 있어서 그런지, discussion이 활성화 돼있어서 참 좋다. 친절한 분들의 친절한 설명이 많다. 아무튼, 그런데 설명을 봐도 뭐가 뭔지 잘 모르겠다 싶었다. DP는 일반적으로 생각하는 방식과 달라서, 반대로 Greedy는 너무 직관적인 때가 많아서 어렵다는 생각이 든다. (대충 다 어렵다는 뜻)

풀이

다시 문제로 돌아와서, DP든 Greedy든 어떤 원소들은 지우는 게 항상 이득인 때가 있다. 이전 원소와 값이 같거나, positive/negative의 상태가 같을 때가 그렇다. 지우지 않으면 풀이를 종료해야 하기 때문이다. 그런데, 그런 원소들을 다 지우면 자연스럽게 Wiggle Sequence만 남는다. 값이 같거나 상태가 같은 원소를 다 지워버렸기 때문이다.

예를 들어 배열을 이전 항과의 상대적 상태로 표현했을 때 (상태: +,-,0), 000+++-+--++--- -> 0+-+-+-가 된다. 즉, 첫 원소를 제외하고 0(이전 항과 같음)은 모두 제거되고, 연속된 '+'나'-'는 하나만 남게 된다. 따라서, 이 작업만 해주면 자연스럽게 정답을 찾게 된다

 

그런데 조금 생각해보니까 뭔가 이상하다. 위의 예시 000+++-+--++---에서 숫자로 직접 해보면, 연속된 상태에서도 어떤 값을 지우느냐에 따라서 길이가 달라진다. 나는 이 부분을 이해하는 데 애를 먹었고, 사실 완벽하게 이해하지 못했다. 그래서 아이디어로 설명을 대신해보려고 한다. 배열 a,b,....,c,d (a<b, c>d)가 있을 때, (a,b)와 (c,d)는 b<c, b==c, b>c 상관 없이 항상 길이 3으로 연결할 수 있다.

코드

class Solution {
    fun wiggleMaxLength(nums: IntArray): Int {
        if (nums.size <= 1) {
            return nums.size
        }
        
        var answer = 1
        var prevDiff = 0
        
        for (i in 1 until nums.size) {
            val diff = nums[i-1] - nums[i]
            
            // 이전 두 수의 상태와 다른 경우
            // 등호를 통해 첫 원소와 연속해서, [5 5 5 3]처럼 처음에 같은 수들이 나오는 것도 처리할 수 있다
            if ((prevDiff >= 0 && diff < 0) || (prevDiff <= 0 && diff > 0)) {
                answer++
                prevDiff = diff
            }
        }
        
        return answer
    }
}

피드백

이해하기 어려운 부분이 DP와 관련이 있을 것 같다. DP 문제도 좀 꾸준히 풀어야지.

혼자 공부 특) 막히는 부분 해결하기 어려움ㅠㅠ