[LeetCode] 48. Rotate Image 풀이 (Java)

 

✔️ 오늘의 리트코드 공부 기록 – Rotate Image

---

 

문제 요약 (Longest Palindromic Substring)

NxN 행렬이 주어지고, 시계 방향으로 90도 회전한다. 단, 추가 배열 없이(in-place) 해결해야 한다.

 

문제링크: https://leetcode.com/problems/rotate-image

 

 

🤔 처음 떠올린 아이디어

처음 문제를 봤을 때는 이렇게 생각했다.

“값을 하나씩 옮기면 되지 않을까?”

 

하지만 하나씩 옮기면 값이 사라지고, in-place 조건 때문에 임시 배열을 사용할 수도 없다.

여기서 생각한 것은, 그럼 값이 사라지기 전에 이 값을 temp 라는 변수에 저장해야겠다라고 생각했다.

 

그래서 자연스럽게 이런 질문으로 이어졌다.

그럼 어떤 값을 먼저 옮기고,
어떤 값을 temp에 저장해야 하지?

 

이 고민을 하다 보니 관점이 조금씩 바뀌기 시작했다.

---

💡 핵심 깨달음: 항상 4개가 한 세트

90도 회전을 그림으로 보면 항상 이 구조다.

top → right 
right → bottom 
bottom → left 
left → top

 

 

즉,

• 어떤 한 칸을 기준으로
• 항상 4개의 좌표가 원형으로 자리만 바꾼다

그래서 이 문제는 결국,

4개의 값을 동시에 swap 하는 문제

로 바뀐다.

나는 여기서 이렇게 정리했다.

• 현재 위치를 temp에 저장한다
• 반시계 방향에 있는 값들을 먼저 이동시킨다
• 마지막에 temp를 빈 자리에 넣는다

---

🧠 Layer 단위로 쪼개기

그럼 이 4-way swap을 얼마나 반복해야 할까?

우선 가장 먼저 바깥 테두리가 돌아갈 것이다.
그러면 또 그 안에 또 작은 정사각형이 남는다.

 

[ layer 0 ]
  [ layer 1 ]
    [ layer 2 ]

 

즉, n/2 만큼의 정사각형이 나오므로 반복 횟수는 자연스럽게 n / 2가 된다.

for (inti=0; i < n / 2; i++) // layer

• i = 0 → 가장 바깥 레이어
• i = 1 → 그 안쪽 레이어

👉 바깥 테두리를 한 번 회전하고, 안쪽 정사각형 layer를 반복 처리한다.

---

한 layer 안에서 무엇만 보면 될까?

한 layer 안에서 실제로 순회해야 할 부분은 윗줄(top row) 하나뿐이다.

왜냐하면:

• top 하나를 기준으로
• left / bottom / right가 자동으로 결정되기 때문

for (int j = i; j < n - 1 - i; j++)

 

• j는 top row에서 움직이는 포인터
• n - 1 - i는 현재 layer의 끝

---

좌표를 기하적으로 대응시키기

기준 좌표를 하나 잡는다.

(i, j) // top

 

 

top	(i, j)
left	(n-1-j, i)
bottom	(n-1-i, n-1-j)
right	(j, n-1-i)

 

이 좌표가 시계 방향으로 회전하면 다음과 같이 이동한다.

int temp = matrix[i][j];                          // top
matrix[i][j] = matrix[n - 1 - j][i];              // left → top
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; // bottom → left
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; // right → bottom
matrix[j][n - 1 - i] = temp;                      // top → right

---

코드 (Java)

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - 1 - i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = temp;
            }
        }
    }
}

 

 

---

🔹 두 번째 방법: Transpose + Reverse

문제를 풀고 나니 “Transpose 한 다음 row를 reverse 하라"는 다른 풀이도 발견했다.

처음 들으면 직관적이지 않지만, 실제로 같은 결과를 만들어낸다.

Transpose란?

행과 열을 서로 바꾸는 것 (i,j → j,i)

예시:

1 2 3      1 4 7
4 5 6  →   2 5 8
7 8 9      3 6 9

 

즉, 대각선 기준으로 서로 자리를 바꾼다고 생각하면 된다.

 

 

여기서 90도 시계 회전의 실제 좌표 이동은 이렇다.

(i, j) → (j, n - 1 - i)

 

이걸 자세히 보면,

(i,j) → (j,i)        // Transpose
       → (j,n-1-i)    // 해당 행 뒤집기

 

즉,

회전은 사실
Transpose + Reverse 두 단계로 쪼갤 수 있는 변환

 

이다.

---

 

코드(Java)

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }
    }
}

 

📈 시간/공간 복잡도

• 시간: 모든 원소를 한 번씩 방문 → O(N²)
• 공간: 추가 배열 없음 → O(1)

---

두 방법은 결국 같은 일을 한다

	4-way swap	Transpose + Reverse
출발점	회전 그 자체	좌표 변환 분해
사고 방식	기하 / 공간 감각	공식 / 변환
즉석 유도	가능했음	어려울 것 같다..
구현 안정성	보통	높음

 

📝 이번 문제에서 얻은 깨달음

• 2D 배열 회전 문제는 layer/좌표 사고가 핵심
• 4-way swap: 직관적으로 유도 가능
• Transpose + Reverse: 알고 있으면 편리한 공식

👉 결국 중요한 건
“공식을 외웠는가"가 아니라, “회전을 어떻게 이해했는가”다.