[알고리즘] 가장 긴 바이토닉 수열 - javascript

📌 문제

📌 풀이 1 : 시간복잡도 O(n제곱)

function bitonic(nums) {
  let n = nums.length;
  let i = 0;
  while (i + 1 < n && nums[i] < nums[i + 1]) ++i;
  if (i === 0 || i === n - 1) return false;
  while (i + 1 < n && nums[i] > nums[i + 1]) ++i;
  if (i !== n - 1) return false;
  return true;
}
function solution_nn(nums) {
  let ans = 0;
  for (let j = 0; j < nums.length; j++) {
    for (let k = j + 2; k < nums.length; k++) {
      let arr = new Array();
      arr = nums.slice(j, k + 1);

      if (bitonic(arr)) {
        if (arr.length >= 3) {
          ans = Math.max(ans, arr.length);
        }
      }
    }
  }
  return ans;
}
console.log(solution_nn([1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6, 5, 7])); // 답 : 9

✔ bitonic함수는 배열을 인자로 받아서 그 배열이 바이토닉 수열이면 true를 반환하는 함수이다.

✔ slice로 인덱스 j부터 k까지 배열을 자르고 그안의 배열이 바이토닉 수열인지 미리 구현해놓았던 bitonic 함수에 인자로 넣어 true이고 수열의길이가 3이상인 경우 max와 비교해서 답인 ans변수에 넣는다.

✔ slice할때 j,k 변수를 이용해 이중 for문을 돌기 때문에 시간복잡도는 O(n2)을 갖는다.

📌 풀이 2 : 시간복잡도 O(n)

function solution_n(nums) {
  let num_length = nums.length;
  let arr_left = new Array(num_length);
  let arr_right = new Array(num_length);
  let ans = 0;
  arr_left[0] = 1;
  arr_right[num_length - 1] = 1;
  for (let i = 1; i < num_length; i++) {
    if (nums[i] > nums[i - 1]) {
      arr_left[i] = arr_left[i - 1] + 1;
    } else if (nums[i] <= nums[i - 1]) {
      arr_left[i] = 1;
    }
  }
  for (let i = num_length - 2; i >= 0; i--) {
    if (nums[i] > nums[i + 1]) {
      arr_right[i] = arr_right[i + 1] + 1;
    } else {
      arr_right[i] = 1;
    }
  }
  for (let i = 0; i < num_length - 1; i++) {
    ans = Math.max(ans, arr_left[i] + arr_right[i + 1]);
  }
  if (ans < 3) {
    ans = 0;
  }
  return ans;
}

console.log(solution_n([1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6, 5, 7])); // 답 : 9

✔ nums 배열에서 왼쪽(인덱스0)부터 오른쪽으로 연속증가횟수를 저장하는 배열 arr_left, 오른쪽(인덱스 nums.length-1)부터 왼쪽으로 연속증가 횟수를 저장하는 배열 arr_right을 선언

✔ 연속증가횟수를 저장한 arr_left, arr_right 배열을 이용하여 arr_left[i] + arr_right[i + 1] 값을 통해 ans와 비교하여 크면 ans를 갱신

✔ 빨간색 부분수열이 arr_left[i] + arr_right[i + 1] 이 9로 가장 긴 바이토닉 수열이고 그 수열의 길이는 9이다. 따라서 ans는 9가 된다.

✔ n번 순회하는 for문을 3개 갖고있지만 모두 개별 for문으로 시간복잡도는 O(n)