[리트코드] 1260 - Shift 2D Grid

1260. Shift 2D Grid

Easy

---

Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift operation:

• Element at grid[i][j] moves to grid[i][j + 1].
• Element at grid[i][n - 1] moves to grid[i + 1][0].
• Element at grid[m - 1][n - 1] moves to grid[0][0].

Return the 2D grid after applying shift operation k times.

 

Example 1:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

Example 2:

Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

Example 3:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m <= 50
• 1 <= n <= 50
• -1000 <= grid[i][j] <= 1000
• 0 <= k <= 100

분류

배열, 행렬, 시뮬레이션

---

문제 풀이

문제 분석

이 문제는 2차원 격자(grid)를 1차원으로 평탄화했을 때, 오른쪽으로 k번 회전(shift)시킨 결과를 다시 원래의 2차원 형태(m x n)로 복원하여 반환하는 것을 요구합니다.

• 입력: m x n 크기의 2차원 정수 리스트 grid, 정수 k
• 출력: k번 시프트 연산을 적용한 후의 m x n 크기 2차원 정수 리스트
• 시프트 규칙:
  1. grid[i][j] → grid[i][j+1] (같은 행 내 오른쪽 이동)
  2. grid[i][n-1] → grid[i+1][0] (행의 끝에서 다음 행의 처음으로 이동)
  3. grid[m-1][n-1] → grid[0][0] (마지막 요소에서 첫 번째 요소로 순환 이동)
• 제약 사항: m, n 최대 50, k 최대 100으로 크기가 작아 O(m*n) 알고리즘으로 충분히 해결 가능합니다.

---

접근 방법

이 문제를 해결하기 위해 1차원 리스트로의 평탄화(Flattening) 후 회전 기법을 사용했습니다.

1. 평탄화: 2차원 그리드를 행 우선 순서(Row-major order)로 1차원 리스트로 변환합니다. 이렇게 하면 복잡한 2차원 인덱스 계산 없이 단순 리스트 연산으로 시프트를 구현할 수 있습니다.
2. 모듈러 연산으로 최적화: k가 전체 요소의 개수(m * n)보다 클 수 있으므로, k % (m*n)을 수행해 실제 필요한 최소 회전 횟수만 계산합니다. 만약 나머지가 0이면 원본을 그대로 반환합니다.
3. 리스트 슬라이싱으로 회전: 파이썬의 슬라이싱 기능(list[-k:] + list[:-k])을 이용해 오른쪽으로 k번 회전한 새 리스트를 O(N) 시간에 생성합니다.
4. 복원: 회전된 1차원 리스트를 다시 m x n 크기의 2차원 리스트로 변환하여 반환합니다.

이 방식은 직관적이며 파이썬의 강력한 리스트 연산을 활용해 구현이 간결하고 효율적입니다.

---

구현 설명

1단계: 그리드 평탄화 (1차원 리스트 변환)

• 이중 반복문을 통해 2차원 grid의 모든 요소를 행 우선 순서로 grid_list라는 1차원 리스트에 순차적으로 추가합니다.
• 예: [[1,2,3],[4,5,6]] → [1,2,3,4,5,6]

2단계: 유효 시프트 횟수 계산 및 예외 처리

• k %= len(grid_list) 연산으로 전체 길이보다 큰 k를 유효한 범위(0 ~ 길이-1)로 줄입니다.
• 만약 k == 0이면 위치 변화가 없으므로 원본 grid를 바로 반환하여 불필요한 연산을 방지합니다.

3단계: 리스트 슬라이싱을 이용한 회전 수행

• answer_list = grid_list[-k:] + grid_list[:-k] 구문으로 오른쪽으로 k칸 회전된 새 리스트를 만듭니다.
• grid_list[-k:]: 뒤에서 k개 요소 (맨 뒤로 갈 요소들)
• grid_list[:-k]: 앞에서부터 뒤에서 k개 제외한 요소 (앞으로 당겨질 요소들)
• 이 두 리스트를 연결하면 원하는 회전 결과가 됩니다.

4단계: 2차원 그리드 복원

• 회전된 1차원 answer_list를 다시 n행 m열의 2차원 리스트 answer로 변환합니다.
• i행 j열에 들어갈 값은 1차원 리스트의 i * m + j 인덱스에 해당합니다. 이를 이중 반복문으로 채워 넣습니다.

---

⏱복잡도 분석

• 시간 복잡도: O(m * n)

  • 평탄화: O(m*n)
  • 슬라이싱 및 새 리스트 생성: O(m*n)
  • 2차원 복원: O(m*n)
  • 모든 과정이 전체 요소 수에 비례하므로 총 O(m*n)입니다.

• 공간 복잡도: O(m * n)

  • 평탄화된 리스트 grid_list: O(m*n)
  • 회전된 리스트 answer_list: O(m*n)
  • 결과 저장을 위한 answer: O(m*n)
  • 입력 크기에 비례하는 추가 공간을 사용하므로 O(m*n)입니다. (입력 자체를 수정하는 In-place 방식이었다면 O(1) 가능하지만, 여기서는 새 리스트를 생성합니다.)

---

핵심 포인트

1. 2차원 인덱스 계산을 1차원으로 단순화: 복잡한 행/열 경계 조건 처리(행 끝에서 다음 행 처음으로 이동 등)를 1차원 리스트의 순환 회전 문제로 치환하여 로직을 단순화했습니다.
2. 모듈러 연산(%)으로 불필요한 연산 제거: k가 그리드 전체 크기보다 큰 경우 나머지만큼만 회전하면 결과가 동일하므로, k %= 총_요소_수를 통해 연산 횟수를 최소화했습니다.
3. 파이썬 리스트 슬라이싱 활용: list[-k:] + list[:-k] 구문으로 별도의 반복문 없이 직관적이고 빠르게 리스트 회전을 구현했습니다. 이는 파이썬에서 시프트/회전 문제를 풀 때 매우 유용한 패턴입니다.

풀이 코드

class Solution:
    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        n = len(grid)
        m = len(grid[0])
        grid_list = []
        for x in grid:
            for y in x:
                grid_list.append(y)

        k %= len(grid_list)
        if k == 0:
            return grid

        answer_list = grid_list[-k:] + grid_list[:-k]
        answer = []
        for i in range(n):
            tmp = []
            for j in range(m):
                tmp.append(answer_list[i*m+j])
            answer.append(tmp)

        return answer