[백준] 16925번 배열 돌리기 1 파이썬 풀이

https://www.acmicpc.net/problem/16926

16926번: 배열 돌리기 1

---

1. 접근 방식

• deque()를 사용해서 배열을 line으로 접근하자.

4 x 4 배열에서 나오는 2개의 line

위 그림처럼 배열을 line으로 접근한다. 사각형 한 줄이 하나의 line인 것이다.

line을 만들기 위해서는 인덱스 처리를 통해 for문으로 배열을 색깔별로 접근하면 된다. 하나의 라인을 만들기 위해 4개의 방향으로 접근한다.

각 line은 deque 자료구조로 표현된다. 일반 리스트가 아니라 deque를 사용하는 이유는 리스트의 맨 앞에 원소를 추가할 때 시간 복잡도가 훨씬 빠르기 때문이다. 일반 리스트는 O(n)이지만, deque 자료구조에서는 O(1) 시간 복잡도를 갖는다.

 

 

• r번 회전하는 것은 각 line마다 맨 뒤 원소를 맨 앞에 추가하는 과정을 r번 반복하는 것이다.

1번 회전

가장 바깥쪽 line을 한 번 회전하는 경우를 살펴보자. 마지막 원소인 2를 맨 앞에 추가하고나서 다시 배열로 만들어 본다면 오른쪽 그림처럼 2가 (0, 0)의 원소로 들어간다. 즉, 1번 회전한 결과이다.

 

 

• 회전한 line을 다시 기존 배열에 적용하자.

처음에 각 line을 만들기 위해 작성했던 인덱스 처리 코드를 그대로 활용한다. 예를 들면 아래와 같다.

for p in range(i, n - i - 1):
    dq.append(array[p][i]) # line 만드는 코드
    
    array[p][i] = lines[i].popleft() # 기존 배열에 회전 결과 삽입하는 코드

 

 

 

 

2. 정답 코드

from collections import deque
import sys

input = sys.stdin.readline

n, m, r = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(n)]

# 1) lines 리스트에 각 라인(deque) 담기
lines = []
for i in range(min(n, m) // 2):
    dq = deque()

    for p in range(i, n - i - 1):
        dq.append(array[p][i])

    for q in range(i, m - i - 1):
        dq.append(array[n - i - 1][q])

    for p in range(n - i - 1, i, -1):
        dq.append(array[p][m - i - 1])

    for q in range(m - i - 1, i, -1):
        dq.append(array[i][q])

    lines.append(dq)

# 2) r번 회전하기
for _ in range(r):
    for line in lines:
        line.appendleft(line.pop())

# 3) 기존 배열에 r번 회전한 결과 삽입하기
for i in range(min(n, m) // 2):
    for p in range(i, n - i - 1):
        array[p][i] = lines[i].popleft()

    for q in range(i, m - i - 1):
        array[n - i - 1][q] = lines[i].popleft()

    for p in range(n - i - 1, i, -1):
        array[p][m - i - 1] = lines[i].popleft()

    for q in range(m - i - 1, i, -1):
        array[i][q] = lines[i].popleft()

# 4) 출력
for row in array:
    print(" ".join(map(str, row)))

 

 

 

3. pypy로만 통과되는 기존 코드

처음에는 deque()가 아니라, 직접 배열을 인덱스별로 접근하여 수정하는 방식으로 코드를 작성했다. 비록 python으로는 시간 초과가 나지만, 해당 코드가 로직이 더 깔끔하고 명확하게 표현되는 듯하여 기록해둔다.

import sys

input = sys.stdin.readline

n, m, r = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(n)]

for _ in range(r):
    for i in range(min(n, m) // 2):
        x, y = i, i
        pre = array[x][y]

        for p in range(x + 1, n - i):
            cur = array[p][y]
            array[p][y] = pre
            pre = cur

        for q in range(y + 1, m - i):
            cur = array[n - i - 1][q]
            array[n - i - 1][q] = pre
            pre = cur

        for p in range(n - i - 2, x - 1, -1):
            cur = array[p][m - i - 1]
            array[p][m - i - 1] = pre
            pre = cur

        for q in range(m - i - 2, y - 1, -1):
            cur = array[x][q]
            array[x][q] = pre
            pre = cur

for row in array:
    print(" ".join(map(str, row)))