LeetCode - Wiggle Subsequence (Javascript)

문제 설명

앞 숫자와의 차이가 음수양수 또는 양수음수의 순서로 일정하게 반복되는 수열을 wiggle subsequence라고 한다.

따라서, 주어진 배열 내에서 wiggle subsequence의 최대 길이를 구해주면 된다!. 주의할 점은 주어진 배열이 고정된 것이 아니라, 배열 내에서 요소의 삭제를 통해 wiggle subsequence를 구현할 수도 있다는 것이다.

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.

• For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.
• In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.

A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Given an integer array nums, return the length of the longest wiggle subsequence of nums.

Example 1:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

Example 2:

Input: nums = [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length.
One is [1, 17, 10, 13, 10, 16, 8] with differences (16, -7, 3, -3, 6, -8).

Example 3:

Input: nums = [1,2,3,4,5,6,7,8,9]
Output: 2

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

---

소스 코드

이번에는 한 번에 좋은 시간 효율성을 갖는 코드를 작성할 수 있었다..!!

function wiggleMaxLength(nums) {
  if (nums.length === 1) return 1;
  let answer = 0;
  let plus = 1;
  let minus = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > nums[i - 1]) plus = minus + 1;
    else if (nums[i] < nums[i - 1]) minus = plus + 1;
  }
  answer = Math.max(plus, minus);
  return answer;
}

---

소스 코드 (조금 더 직관적인 풀이법)

1번 코드는 조금 직관적이지가 않은 것 같다는 생각이 들었다.
따라서 조금 더 직관적으로 이해할 수 있는 코드를 아래와 같이 작성해봤다.

function wiggleMaxLength(nums) {
  if (nums.length < 2) return nums.length;
  let count = 1;
  let prevDiff = 0;
  const stack = [];
  for (let i = 1; i < nums.length; i++) {
    let currentDiff = nums[i] - nums[i - 1];
    if (
      (currentDiff > 0 && prevDiff <= 0) ||
      (currentDiff < 0 && prevDiff >= 0)
    ) {
      count++;
      prevDiff = currentDiff;
      stack.push(currentDiff);
    }
  }
  console.log(stack);
  return count;
}

---

풀이 설명

plus와 minus의 최대 경우의 수를 비교연산을 통해 구할 수 있었다.

우측 - 좌측의 연산을 반복문을 돌며 계속 진행한다.

그리고 그 연산 결과가 양수면 plus = minus+1, 음수면 minus = plust + 1을 해준다. 이렇게 양수일 때는 음수일 때의 경우의수+1, 음수일 때는 양수일 때의 경우의 수+1을 해주는 이유는 무엇일까?

위의 예시를 살펴보도록 하자.

1 → 17 → 5 이후는 plus가 세 번 연속 이어진다. 이 경우는 이렇게도 해석할 수 있는데, 5 → 10이던, 5→13이던, 5- → 15던 결과는 양수라는 것이다. 따라서 1 → 17 → 5 → 15를 선택하면 그 뒤에 minus가 나오기 때문에 수열을 이어나갈 수 있다.

그리고 그 다음도 마찬가지다. 1 → 17 → 5 → 15 이후에 10을 넣던, 5를 넣던 minus가 두 번 연속되고 있다는 것은 15보다 작은 수들이 두 개 연결되어 있다는 뜻이므로 5를 선택해도 된다. 이에 따라 수열은 1 → 17 → 5 → 15 → 5가 된다. 그리고 그 이후의 수열은 플러스 마이너스가 교차적으로 나타나기 때문에 그냥 뒤의 수들을 연결시켜주면 된다. 그러면 최종적으로 1 → 17 → 5 → 15 → 5 → 16 → 8가 도출될 것이다.

---