[프로그래머스] 행렬 테두리 회전

문제 분석

문제 요구사항

• 입력: rows, columns (2 이상 100 이하 자연수), queries (회전할 영역 배열)
• 기준 배열: 1부터 rows×columns까지 순서대로 채워진 행렬
• 동작: 지정된 직사각형 영역의 테두리를 시계방향으로 1칸씩 회전
• 출력: 모든 회전이 완료된 최종 행렬

예시 이해

2×2 기준배열: [[1,2], [3,4]]
쿼리 [1,1,2,2]: 전체 테두리 회전
결과: [[3,1], [4,2]]

접근 방법

1단계: 기준 배열 생성

const matrix = [];
for (let i = 0; i < rows; i++) {
  matrix[i] = [];
  for (let j = 0; j < columns; j++) {
    matrix[i][j] = i * columns + j + 1;
  }
}

2차원 배열을 동적으로 생성하고 각 위치에 순차적인 숫자를 할당한다.

2단계: 테두리 요소 수집

테두리를 시계방향으로 순회하며 요소들을 수집한다:

// 위쪽 행 (왼쪽→오른쪽)
for (let j = c1; j <= c2; j++) {
  temp.push(matrix[r1][j]);
}

// 오른쪽 열 (위→아래, 마지막 요소 제외)
for (let i = r1 + 1; i <= r2; i++) {
  temp.push(matrix[i][c2]);
}

// 아래쪽 행 (오른쪽→왼쪽, 마지막 요소 제외)
for (let j = c2 - 1; j >= c1; j--) {
  temp.push(matrix[r2][j]);
}

// 왼쪽 열 (아래→위, 마지막 요소 제외)
for (let i = r2 - 1; i > r1; i--) {
  temp.push(matrix[i][c1]);
}

3단계: 시계방향 회전

// 마지막 요소를 맨 앞으로 이동 (1칸 회전)
const rotated = [temp[temp.length - 1], ...temp.slice(0, -1)];

4단계: 회전된 값 배치

수집한 순서와 동일하게 회전된 값을 다시 행렬에 배치한다.

핵심 알고리즘

테두리 회전 로직

1. 수집: 테두리 요소들을 시계방향으로 순서대로 수집
2. 회전: 배열의 마지막 요소를 맨 앞으로 이동
3. 배치: 회전된 값들을 원래 순서대로 다시 배치

시간복잡도 분석

• 기준 배열 생성: O(rows × columns)
• 각 쿼리 처리: O(테두리 길이) = O(2×(r2-r1+1) + 2×(c2-c1+1) - 4)
• 전체: O(rows × columns + K × M) (K: 쿼리 개수, M: 평균 테두리 길이)

테스트 케이스

케이스 1: 2×2 행렬

입력: rows=2, columns=2, queries=[[1,1,2,2]]
기준: [[1,2], [3,4]]
회전: 1→2→4→3 → 3→1→2→4
결과: [[3,1], [4,2]]

케이스 2: 3×3 행렬

입력: rows=3, columns=3, queries=[[1,1,2,2]]
기준: [[1,2,3], [4,5,6], [7,8,9]]
회전 영역: [[1,2], [4,5]] (2×2 부분)
결과: [[4,1,3], [5,2,6], [7,8,9]]

핵심 인사이트

1. 테두리 순회 패턴

시계방향 순회는 위→오른쪽→아래→왼쪽 순서로 진행한다. 중복 요소를 방지하기 위해 각 방향에서 마지막 요소를 제외한다.

2. 회전 구현

배열 회전은 단순히 마지막 요소를 앞으로 이동하는 것으로 구현할 수 있다. 복잡한 인덱스 계산 없이 간단하게 구현할 수 있다.

3. 효율성 고려

불필요한 배열 생성을 최소화하고 직접적인 인덱스 접근으로 O(1) 연산을 활용한다.

최적화 포인트

1. 메모리 효율성: 임시 배열 크기를 테두리 길이로 제한
2. 시간 효율성: 각 쿼리를 독립적으로 처리하여 병렬화 가능
3. 코드 가독성: 명확한 주석과 단계별 분리로 유지보수성 향상

성능 분석

최악의 경우는 모든 쿼리가 전체 행렬을 회전하는 경우이다. 공간복잡도는 O(rows × columns)로 원본 행렬 크기와 같다. 실제 성능은 대부분의 경우 테두리 길이가 작아 효율적이다.

이 풀이는 직관적이면서도 효율적인 접근 방식으로, 복잡한 수학적 계산 없이도 정확한 결과를 얻을 수 있다.