JavaScript로 찾는 가장 짧은 미정렬 연속 구간의 길이

문제 이해

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

이 함수는 하나의 연속된 부분 배열(continuous subarray)을 찾아야 합니다. 즉, 해당 부분 배열만 오름차순으로 정렬했을 때 전체 배열 역시 오름차순으로 정렬되도록 만드는 최소 길이의 구간을 구하고, 그 길이를 반환하면 됩니다.

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

const arr = [3, 7, 5, 9, 11, 10, 16];

이때 기대하는 출력은 다음과 같습니다.

const output = 5;

출력 해설

배열 중간의 [7, 5, 9, 11, 10] 구간만 정렬하면 전체 배열이 [3, 5, 7, 9, 10, 11, 16]으로 완전히 정렬되기 때문입니다. 따라서 정렬이 필요한 가장 짧은 구간의 길이는 5가 됩니다.

접근 방법

가장 직관적이고 효율적인 방법은 다음과 같습니다.

원본 배열을 복사한 뒤 오름차순으로 정렬합니다.
원본 배열과 정렬된 배열을 앞에서부터 비교하여 처음으로 값이 달라지는 위치(start)를 찾습니다.
같은 방식으로 뒤에서부터 비교하여 마지막으로 값이 달라지는 위치(end)를 찾습니다.
start와 end 사이의 구간이 바로 정렬이 필요한 최소 범위이며, 그 길이는 end - start + 1입니다.

배열이 이미 정렬되어 있다면 두 포인터가 교차하게 되므로 이 경우 0을 반환하도록 처리합니다.

예시 코드

const arr = [3, 7, 5, 9, 11, 10, 16];
const shortestLength = (arr = []) => {
    const sorted = [...arr].sort((a, b) => a - b)
    let start = 0
    let end = sorted.length - 1
    while (sorted[start] === arr[start] && start < arr.length) {
        start += 1
    }
    while (sorted[end] === arr[end] && end >= 0) {
        end -= 1
    }
    return end >= start ? end - start + 1 : 0
}
console.log(shortestLength(arr));

코드 설명

정렬된 복사본 생성: 스프레드 연산자(...)로 원본 배열을 복사한 후 오름차순으로 정렬합니다. 원본 배열을 훼손하지 않기 위함입니다.
양방향 탐색: start 포인터는 배열의 시작점에서, end 포인터는 끝점에서 출발합니다.
일치 구간 건너뛰기: 앞쪽에서는 원본과 정렬본의 값이 같은 동안 start를 증가시키고, 뒤쪽에서는 값이 같은 동안 end를 감소시켜 이미 정렬된 영역을 제외합니다.
결과 반환: 두 포인터가 교차하지 않았다면 end - start + 1이 곧 정렬해야 하는 최소 구간의 길이이며, 이미 정렬된 배열이라면 0을 반환합니다.

실행 결과

코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.