[LeetCode] 376. Wiggle Subsequence / JAVA

>> 문제설명

leetcode.com/problems/wiggle-subsequence/

Wiggle Subsequence - LeetCode

> 일차원 배열로 주어진 input에서, 계차수열이 양수와 음수가 번갈아 나오도록 하는 가장 긴 subSequence를 구하는 문제이다.

> 문제 설명 상, 순서를 바꾸지 않는다면 원소를 0개 이상 제거한 것이 주어진 배열에 대한 subSequence다.

 

> IDEA

배열에서 이전 숫자보다 현재 숫자가 크면 계차가 양수, 아니면 계차가 음수이므로 현재 숫자와 이전 숫자 비교를 선형으로 진행하였다.

이 과정에서, 숫자가 계속 늘어나는건 계차의 부호가 바뀌지 않기 때문에 isGrowing이라는 Boolean 변수를 선언해 상태를 관리했다.

 

>Solution

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int ans = 1;
        boolean isGrowing =true;
        if(nums.length < 2) return nums.length;
        for(int idx = 1; idx < nums.length; idx++){
            if(nums[idx] > nums[idx-1]){
                if(isGrowing == false){
                    ans++;
                } else if(ans == 1) ans++;
                isGrowing = true;
            } else if (nums[idx] < nums[idx-1]){
                if(isGrowing == true){
                    ans++;
                } else if(ans == 1) ans++;
                isGrowing = false;
            }
        }
        return ans;
    }
}