이번 글에서는 2차원 배열, 즉 반드시 정사각형 형태(n×n)를 이루는 행렬을 입력받아, 그 요소들을 나선형(spiral) 순서로 추출한 새로운 1차원 배열을 반환하는 JavaScript 함수를 작성해 보겠습니다.
예를 들어 다음과 같은 3×3 행렬이 주어졌다고 가정해 봅시다.
const arr = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ];
함수는 왼쪽 상단 모서리인 위치 (0, 0)에서 시작하여 시계 방향으로 안쪽을 향해 나선형으로 요소를 수집해야 합니다. 따라서 위 행렬에 대한 기대 출력은 다음과 같습니다.
const output = [1, 2, 3, 6, 9, 8, 7, 4, 5];
접근 방식: 경계 포인터 활용
가장 효율적인 방법은 행렬의 현재 경계(boundary)를 추적하는 네 개의 변수를 사용하는 것입니다.
startRow: 아직 순회하지 않은 영역의 첫 번째 행 인덱스endRow: 마지막 행 인덱스startCol: 첫 번째 열 인덱스endCol: 마지막 열 인덱스
매 반복마다 위쪽 행 → 오른쪽 열 → 아래쪽 행 → 왼쪽 열 순서로 요소를 수집한 뒤, 각 방향의 시작 값을 증가시키고 끝 값을 감소시켜 경계를 점점 중앙으로 좁혀 나갑니다. 이 과정을 startRow ≤ endRow이고 startCol ≤ endCol인 동안 반복하면 됩니다.
구현 예제
const arr = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ];
const spiral = (arr = []) => {
if (!arr || arr.length === 0) {
return [];
};
let startRow = 0;
let startCol = 0;
let res = [];
let endCol = arr[0].length - 1;
let endRow = arr.length - 1;
while (startRow <= endRow && startCol <= endCol) {
// 1. 왼쪽에서 오른쪽으로: 맨 윗행 순회
for (let i = startCol; i <= endCol; i++) {
res.push(arr[startRow][i]);
}
startRow++;
// 2. 위에서 아래로: 맨 오른쪽 열 순회
for (let i = startRow; i <= endRow; i++) {
res.push(arr[i][endCol]);
}
endCol--;
// 3. 오른쪽에서 왼쪽으로: 맨 아랫행 순회
if (startRow <= endRow) {
for (let i = endCol; i >= startCol; i--) {
res.push(arr[endRow][i]);
}
endRow--;
}
// 4. 아래에서 위로: 맨 왼쪽 열 순회
if (startCol <= endCol) {
for (let i = endRow; i >= startRow; i--) {
res.push(arr[i][startCol]);
}
startCol++;
}
}
return res;
};
console.log(spiral(arr));실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]
코드 설명 및 핵심 포인트
이 알고리즘의 시간 복잡도는 O(n²)입니다. 행렬의 모든 요소를 정확히 한 번씩만 방문하기 때문입니다. 공간 복잡도 역시 결과 배열을 저장하기 위한 O(n²)입니다.
특히 주목할 부분은 세 번째와 네 번째 단계 앞의 조건문입니다. 한 줄짜리 행(row) 또는 한 열짜리 행렬을 처리할 때 같은 요소를 중복해서 추가하는 것을 방지하는 역할을 합니다. 예를 들어 3×1 행렬의 경우, 오른쪽 열을 순회한 후 이미 남은 요소가 없는데도 아랫행과 왼쪽 열을 다시 순회하면 중복이 발생합니다. 이 조건 검사 덕분에 어떤 크기의 직사각형 행렬에서도 올바르게 동작합니다.