백준 구현 대비 배열돌리기2

문제 : https://www.acmicpc.net/problem/16927

접근

한 회전 마다 전체 배열을 시작부터 끝까지 모두 회전시켜 주는 식으로 구현하였으나 회전 하는 경우의 수 r의 최댓값이 10^9이었으므로 바로 시간초과가 발생하였음. r의값 만큼 모두 회전하는 방식으로 구현하면 배열의 크기와 상관없이 무조건 시간초과가 발생함...--> r의 값을 줄일 수 있는 방법을 떠올려야함

r의 값을 줄일 수 있는 방법은 다음에서 힌트를 찾을 수 있음

• 회전해야 하는 배열의 길이가 n이라면, n의 배수만큼 회전하면 결국 원위치임, 즉 r번 회전시키는 것이 아니라 r%n번 회전시켜준다면 연산 횟수를 줄이고 동일한 결과를 산출할 수 있음

• 위 방식을 적용하려면, 한번의 회전에 전 배열을 회전시키는 것이 아니라 각 시작점마다 rotate 함수를 따로 적용시켜 주어야함 (길이가 각각 다르므로)

2번째 코드

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


def rotate(ssi,ssj,n, m):
    # 인덱스 기준으로
    si, ei = ssi, n - 1
    sj, ej = ssj, m - 1
    # n 세로 m 가로
    new_graph = [g[:] for g in graph]

    for i in range(si, ei):
        new_graph[i + 1][sj] = graph[i][sj]

    for j in range(sj, ej):
        new_graph[ei][j + 1] = graph[ei][j]

    for i in range(ei, si , -1):
        new_graph[i - 1][ej] = graph[i][ej]

    for j in range(ej, sj , -1):
        new_graph[si][j - 1] = graph[si][j]

    return new_graph


si,sj,ei,ej=0,0,n,m
while si<ei and sj<ej:
   length=(ei-si)*2+(ej-sj)*2-4
   newr=r%length
   for i in range(newr):
    graph=rotate(si,sj,ei,ej)

   si+=1
   sj+=1
   ei-=1
   ej-=1
for g in graph:
  print(*g)

시작점과 끝점을 분리해서 매개변수로 전달받을 수 있도록 rotate 함수를 구현하였으며, 회전하는 부분의 전체 길이만큼 회전 횟수에서 나머지 연산을 해줘서 불필요한 연산을 줄여주었다.

추가

pypy 로 제출하였을 때는 통과하였으나 python3으로 제출하면 시간초과가 발생하였음, 아마 python으로도 통과하려면 deque 모듈 import 한다음에 이차원 배열을 일차원 배열로 전환한 후 회전연산 해주고 다시 이차원 배열로 복구시키는 식으로 계산해야 될듯.