[백준] 16926 배열 돌리기 1

백준 16926 배열 돌리기 1

2차원 배열을 반시계 방향으로 R번 회전하는 문제다. 처음에는 단순하게 한 칸씩 이동시키는 방식으로 접근했지만, 시간 복잡도가 O(R×N×M) 가 되어 시간 초과가 발생했다. 이를 최적화하기 위해 Deque를 활용한 테두리 단위 회전 방식을 적용했다

import sys
from collections import deque

def solution():
    inp = sys.stdin.readline
    n, m, r = map(int, inp().split())
    grid, dq = [list(map(int, inp().split())) for _ in range(n)], deque()
    t = min(n, m) // 2  # 회전할 테두리 개수

    for i in range(t):
        # Step 1: 테두리 요소를 Deque에 저장
        dq = deque()

        # 위쪽
        dq.extend(grid[i][i: m - 1 - i])
        # 오른쪽
        for y in range(i, n - 1 - i):
            dq.append(grid[y][m - 1 - i])
        # 아래쪽
        dq.extend(grid[n - 1 - i][m - 1 - i: i: -1])
        # 왼쪽
        for y in range(n - 1 - i, i, -1):
            dq.append(grid[y][i])

        # Step 2: R칸 회전 (슬라이싱 활용)
        res = r % len(dq)  # 필요 없는 전체 회전을 방지
        dq = deque(list(dq)[res:] + list(dq)[:res])

        # Step 3: 회전된 결과를 다시 배열에 배치
        for x in range(i, m - 1 - i):
            grid[i][x] = dq.popleft()
        for y in range(i, n - 1 - i):
            grid[y][m - 1 - i] = dq.popleft()
        for x in range(m - 1 - i, i, -1):
            grid[n - 1 - i][x] = dq.popleft()
        for y in range(n - 1 - i, i, -1):
            grid[y][i] = dq.popleft()

    # 결과 출력
    for y in range(n):
        print(*grid[y])

if __name__ == "__main__":
    solution()

문제 해결 과정 및 최적화 과정

1. 단순한 반복 이동 방식의 비효율성

처음에는 배열을 직접 수정하며 한 칸씩 회전하는 방식을 사용했다. 하지만, 이 방식은 O(R×N×M)의 시간 복잡도를 가지기 때문에, 한 번에 R칸씩 회전하여 불필요한 중간 단계를 줄임. 결과적으로 O(N×M)에 문제 해결

2. Deque를 활용한 테두리별 회전

배열의 각 테두리를 하나의 리스트(Deque)로 변환하여 회전하면, 한 번의 연산으로 여러 칸을 이동할 수 있다.

1. 각 테두리를 Deque에 저장
   • 2차원 배열의 테두리를 따라 1차원 리스트로 변환
2. Deque 슬라이싱을 활용해 R칸 회전
   • 기존 방식은 O(R)의 연산이 필요했지만, 슬라이싱을 사용하면 O(1)에 가능
3. 모듈러 연산을 활용한 슬라이싱 오류 방지
   • 2차원 배열의 테두리를 따라 1차원 리스트로 변환
   • deque = deque[r:] + deque[:r] 형태로 한 번에 이동
4. 회전된 데이터를 다시 배열에 적용
   • Deque에서 값을 하나씩 꺼내 원래 위치에 삽입