[코테] 백준 시물레이션과 구현 16927번 문제

16927번 : 배열 돌리기 2

문제 링크

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

문제 설명

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

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

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

출력

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

제한

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

문제풀이

이번 배열 돌리기 문제에서 회전수가 많아진 문제이다. 따라서 이전과 같은 방식으로 풀이하면 시간초과가 발생한다.

1. 배열 안에서 작은 배열 회전을 진행하게 되는데 각 작은 배열의 원소를 순서에 맞게 1차원 배열로 저장 및 원소 개수를 저장해놓는다.
2. 각 작은 배열의 회전 수는 회전수에 원소개수를 나눈 나머지이다.
3. 각 작은 배열을 순회하면서 새로운 dp배열에 값을 입력한 이후 dp배열을 출력한다.

def rotation() :
    dp = [[0 for _ in range(M)] for _ in range(N)]
    poolingArray = []

    # 배열 내 작은 배열들을 순서에 맞게 1차원 배열로 저장한다.
    for k in range(min(N, M) // 2) :
        temp = []
        for i in range(k, N-k) :
            temp.append(arr[i][k])
        for j in range(k+1, M-k) : 
            temp.append(arr[i][j])
        for i in range(i-1, k-1, -1) :
            temp.append(arr[i][j])                        
        for j in range(j-1, k, -1) :
            temp.append(arr[i][j])
        poolingArray.append(temp)

    # 각 작은 배열의 회전 수를 저장한다. 
    iter = []
    for temp in poolingArray :
        iter.append(R % len(temp)) 

    # 각 작은 배열을 회전시킨 이후의 순서대로 dp배열에 저장한다.
    for k in range(min(N, M) // 2) :
        idx = (len(poolingArray[k]) - iter[k]) % len(poolingArray[k])
        
        for i in range(k, N-k) :
            dp[i][k] = poolingArray[k][idx]
            idx = (idx + 1) % len(poolingArray[k])
            
        for j in range(k+1, M-k) : 
            dp[i][j] = poolingArray[k][idx]
            idx = (idx + 1) % len(poolingArray[k])
            
        for i in range(i-1, k-1, -1) :
            dp[i][j] = poolingArray[k][idx]
            idx = (idx + 1) % len(poolingArray[k])
            
        for j in range(j-1, k, -1) :
            dp[i][j] = poolingArray[k][idx]
            idx = (idx + 1) % len(poolingArray[k])
    
    return dp

N, M, R = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
dp = rotation()
for i in range(len(dp)) :
    print(" ".join(map(str, dp[i])))