[ProblemSolving] 백준 - 16927 배열돌리기2(구현>행렬)

문제 링크

문제 설명

배열 돌리기1과 같은 문제입니다.

다른 점은 제한 조건

2 ≤ N, M ≤ 300
1 ≤ R ≤ 10^9
min(N, M) mod 2 = 0
1 ≤ Aij ≤ 10^8

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

예제 입력1

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

예제 출력1

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

나의 풀이

배열 돌리기 1 같은 경우, 회전 횟수(1000) 만큼 탐색한다.
하지만 배열 돌리기 2 에서는 회전 횟수가 10^9 이므로 시간 복잡도를 낮춰야 한다.

예를 들어, 4x4 배열이 13바퀴를 돌린 것은 1바퀴를 돌린 것과 같으므로,
여기서는 불필요한 회전을 하지 않고, deque의 rotate()를 사용하여 해결한다.

deque를 사용하는 이유는 큐보다 append와 pop이 압도적으로 빠르고,
양끝 요소에 접근하여 삽입, 삭제 하는 경우, 리스트는 O(n), deque O(1)로 가능하다.

deque 문법

from collections import deque

deq = deque()

# Add element to the start
deq.appendleft(10)

# Add element to the end
deq.append(0)

# Pop element from the start
deq.popleft()

# Pop element from the end
deq.pop()

• rotate 메서드 : 양수 또는 음수값을 파라미터로 주어 좌, 우 회전 가능
  1 : 좌 -> 우 // -1: 우 -> 좌

# Contain 1, 2, 3, 4, 5 in deq
deq = deque([1, 2, 3, 4, 5])
deq.rotate(1)
print(deq)
# deque([5, 1, 2, 3, 4])
deq.rotate(-1)
print(deq)
# deque([1, 2, 3, 4, 5])

• 필요성
  리스트보다 월등한 연산 속도 제공

코드

from collections import deque

def rotate(x, y, height, width):
    #global graph
    q = deque()
    # 윗변 왼 -> 오른
    for i in range(y, y+width):
        q.append(graph[x][i])
    # 오른변 위 -> 아래
    for i in range(x+1, x+height):
        q.append(graph[i][y+width-1])
    # 밑변 오른 -> 왼
    for i in range(y+width-2, y, -1):
        q.append(graph[x+height-1][i])
    # 왼변 아래 -> 위
    for i in range(x+height-1, x, -1):
        q.append(graph[i][y])
    q.rotate(-r)
    
    for i in range(y, y+ width):
        graph[x][i] = q.popleft()
    
    for i in range(x+1, x+height):
        graph[i][y+width-1] = q.popleft()
    
    for i in range(y+width-2, y, -1):
        graph[x+height-1][i] = q.popleft()
    
    for i in range(x+height-1, x, -1):
        graph[i][y] = q.popleft()
  
n, m, r = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

height = n
width = m
x, y = 0, 0

while True:
    if height == 0 or width == 0: 
        break
    rotate(x, y, height, width)
    x += 1
    y += 1
    height -= 2
    width -= 2
    
for i in graph:
    for j in i:
        print(j, end=" ")
    print()