[백준] 16927번 파이썬 - 배열 돌리기 2

16927번: 배열 돌리기 2

 

16926 번 문제에서 회전 횟수의 범위가 

1 <= R <= 10^9로 늘어난 문제이다.

 

회전 횟수를 줄이기 위해 배열이 몇 번 회전했을 때 현재 배열과 똑같아 지는지 고민해보았고,

2*(n-1) + 2*(m-1)

이와 같은 사이클이 지날 때 마다 배열의 겉 둘레가 처음 배열과 같아지는 것을 확인했다.

for문의 회전 범위를 R % cycle로 줄이고 제출해보니 틀렸다..

 

왜?

16926번 문제에서 나는 다음과 같이 주어진 배열을 r번 회전하기만 했다.

for _ in range(r):
    for i in range(min(n,m)//2):
        rotate(array)

 

for i in range(min(n,m)//2)는 즉 겉에서부터 한 껍질 씩 확인하는 것과 같다.

따라서 이번 문제에선 for문이 한 번 돌아갈 때, 그 때마다 cycle로 회전 횟수를 나누어주고

cycle에서 겉 껍질과 안쪽 껍질의 둘레 차를 빼주며 갱신하주는 방식을 사용해야 했던 것이다.

for i in range(min(n,m)//2):
    for _ in range(r%cycle):
        rotate(array)
    cycle -=8

 

다음과 같이 로직을 바꾸었더니 맞았다!

 

코드

import sys
input = sys.stdin.readline
n,m,r = map(int,input().split())
array = []

for _ in range(n):
    array.append(list(map(int,input().split())))

def rotate(array):
    x,y = i,i
    # 맨 처음 값 저장
    value = array[x][y]

    # 왼쪽
    for j in range(i+1,n-i):
        x = j
        tmp = array[x][y]
        array[x][y] = value
        value = tmp

    # 아래쪽
    for j in range(i+1, m-i): 
        y = j
        tmp = array[x][y]
        array[x][y] = value
        value = tmp

    # 오른쪽
    for j in range(i+1, n-i): 
        x = n - j - 1 
        tmp = array[x][y] 
        array[x][y] = value
        value = tmp

    # 위
    for j in range(i+1, m-i):
        y = m - j - 1
        tmp = array[x][y]
        array[x][y] = value
        value = tmp
    return array

cycle = 2*(n-1) + 2*(m-1)
for i in range(min(n,m)//2):
    for _ in range(r%cycle):
        rotate(array)
    cycle -=8

for i in array:
    print(*i)