JavaScript로 배열을 증가하는 시퀀스로 변환할 수 있는지 확인하는 방법

증가 시퀀스란 무엇인가?

배열이 증가(increasing)한다고 정의하려면, 모든 인덱스 i(0 ≤ i ≤ n-2)에 대해 다음 조건이 성립해야 합니다.

arr[i] <= arr[i + 1]

즉, 배열의 각 요소가 바로 뒤에 오는 요소보다 작거나 같아야 한다는 의미입니다.

문제 정의

정수 배열 arr를 첫 번째이자 유일한 인자로 받는 JavaScript 함수를 작성해야 합니다.

이 함수의 목표는 배열의 최대 한 개의 요소만 수정해서 해당 배열을 증가하는 배열로 만들 수 있는지 판단하는 것입니다.

변환이 가능하다면 true를 반환합니다.
불가능하다면 false를 반환합니다.

입력 및 출력 예시

예를 들어 함수에 다음과 같은 배열이 주어졌다고 가정해 보겠습니다.

입력

const arr = [8, 3, 3, 7, 9];

출력

const output = true;

출력 설명

인덱스 0에 있는 값 8을 1 또는 2로 교체하면 [1, 3, 3, 7, 9] 또는 [2, 3, 3, 7, 9]가 되어 증가하는 배열을 얻을 수 있기 때문입니다.

구현 코드

다음은 이 문제를 해결하는 코드입니다.

const arr = [8, 3, 3, 7, 9];
const canConvert = (arr = []) => {
   const find = () => {
      for (let i = 1; i < arr.length; i++) {
         if (arr[i] < arr[i - 1]) {
            return false;
         }
      }
      return true;
   }
   for (let i = 0; i < arr.length; i++) {
      if (arr[i] < arr[i - 1]) {
         const temp = arr[i];
         arr[i] = arr[i - 1];
         if (find(arr)) {
            return true;
         }
         arr[i] = temp;
         arr[i - 1] = arr[i];
         return find(arr);
      }
   }
   return true;
}
console.log(canConvert(arr));

코드 동작 원리

이 알고리즘은 다음과 같은 단계로 동작합니다.

내부에 정의된 find() 헬퍼 함수는 현재 배열이 이미 증가하는 배열인지 검사합니다.
외부 반복문을 돌면서 처음으로 감소하는 구간(arr[i] < arr[i-1])을 발견하면, 두 가지 수정 전략을 순서대로 시도합니다.
- 첫 번째 시도: 현재 요소 arr[i]를 이전 요소 arr[i-1]과 같은 값으로 올려서 확인합니다.
- 두 번째 시도: 첫 번째 방법이 실패하면, 이전 요소 arr[i-1]을 현재 요소 arr[i]와 같은 값으로 내려서 다시 확인합니다.
두 가지 시도 중 하나라도 증가하는 배열을 만들 수 있다면 true를 반환하고, 그렇지 않다면 false를 반환합니다.
처음부터 감소하는 구간이 없다면 수정 없이도 조건을 만족하므로 true를 반환합니다.

실행 결과

true

위 예시에서는 값 8만 수정하면 되기 때문에 함수는 true를 반환합니다.

시간 복잡도

최악의 경우 배열을 여러 번 순회하게 되지만, 실질적으로는 감소 구간을 발견한 지점 근처에서만 추가 검사가 일어나므로 대체로 O(n) 수준의 효율성을 기대할 수 있습니다. 공간 복잡도는 추가 배열을 사용하지 않으므로 O(1)입니다.