JavaScript로 -1, 0, 1 세 가지 값만 있는 배열을 한 번의 순회로 정렬하는 방법

정확히 세 가지 고유한 값, 즉 -1, 0, 1만 다양한 빈도로 포함하는 숫자 배열이 있다고 가정해 보겠습니다.

const arr = [1, 1, 0, -1, 1, 0, -1, 1, 0, 0, 1];

이런 배열을 입력으로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 별도의 추가 배열을 사용하지 않고 제자리(in-place)에서 배열을 정렬해야 합니다.

여기서 중요한 조건은 함수가 선형 시간(O(n))에 동작해야 한다는 점입니다. 즉, 배열을 딱 한 번만 순회하면서 정렬을 완료해야 합니다.

접근 방식: 네덜란드 국기 알고리즘(Dutch National Flag)

이 문제는 세 개의 포인터(left, middle, right)를 활용하는 네덜란드 국기 알고리즘으로 우아하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• left: -1이 위치해야 할 영역의 경계를 가리킵니다.
• middle: 현재 검사 중인 요소를 가리킵니다.
• right: 1이 위치해야 할 영역의 경계를 가리킵니다.

현재 요소가 -1이면 왼쪽 영역과 교환하고, 0이면 그대로 두고 다음으로 진행하며, 1이면 오른쪽 영역과 교환합니다. 단, 오른쪽과 교환할 때는 교환된 값이 아직 검사되지 않았으므로 middle 포인터를 이동시키지 않는 것이 핵심입니다.

구현 코드

const arr = [1, 1, 0, -1, 1, 0, -1, 1, 0, 0, 1];

const sortSpecialArray = (arr = []) => {
   const swap = (a, b) => {
      let temp = arr[a];
      arr[a] = arr[b];
      arr[b] = temp;
   };
   let left = 0;
   let middle = 0;
   let right = arr.length - 1;
   while (middle <= right) {
      if (arr[middle] === -1) {
         swap(left++, middle++);
      } else if (arr[middle] === 0) {
         middle++;
      } else if (arr[middle] === 1) {
         swap(right--, middle);
      }
   };
};

sortSpecialArray(arr);
console.log(arr);

실행 결과

콘솔 출력 결과는 다음과 같습니다.

[
   -1, -1, 0, 0, 0,
    0, 1, 1, 1, 1,
    1
]

동작 원리와 시간 복잡도

이 알고리즘은 각 요소를 최대 한 번씩만 방문하므로 시간 복잡도가 O(n)입니다. 또한 스왑 연산만 사용하고 추가 배열을 생성하지 않기 때문에 공간 복잡도는 O(1)로, 메모리 측면에서도 매우 효율적입니다.

특히 주목할 부분은 arr[middle] === 1인 경우입니다. 오른쪽 끝의 값과 교환한 후에는 right만 감소시키고 middle은 그대로 유지합니다. 이는 오른쪽에서 가져온 값이 아직 검사되지 않았기 때문이며, 이 처리 덕분에 전체 배열을 정확히 한 번의 순회로 정렬할 수 있습니다.