[BOJ] (구현) 16927번 배열 돌리기 2

 

16926번 배열돌리기1 이랑 문제는 같지만, R의 범위가 아주 크다.

배열을 돌리면 처음상태로 돌아오는 지점이 있을 것이기 때문에, 나머지 연산을 통해 연산 횟수를 줄여주면 된다. 

처음엔 deepcopy를 이용해서 구현을 했는데, 2차원 배열을 deepcopy하는것은  시간이 오래걸리는 작업이기 때문에 시간초과가 발생했다.

 

# 시간초과가 발생했던 코드 

import copy
import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))
    
def f(arr, k):
    start = 0
    end_row = n-1
    end_col = m-1

    tmp = copy.deepcopy(arr)

    while start < end_row and start < end_col:
        for _ in range(k%(2*(end_row+end_col-2*start))):
            #ㅜ
            for i in range(start, end_row):
                tmp[i+1][start] = arr[i][start]

            #ㅏ
            for i in range(start, end_col):
                tmp[end_row][i+1] = arr[end_row][i]

            #ㅗ
            for i in range(end_row, start, -1):
                tmp[i-1][end_col] = arr[i][end_col] 

            #ㅓ
            for i in range(end_col, start, -1):
                tmp[start][i-1] = arr[start][i]
            
            arr = copy.deepcopy(tmp)
            
        start += 1
        end_row -= 1
        end_col -= 1

    return arr

arr = f(arr, k)
    
for a in arr:
    print(*a)

 

 

꽤 오랜시간동안 고민을 했는데, 생각해 낸것은 deque에 한바퀴의 숫자들을 저장한 다음, pop한 요소들을 arr에 재할당 하는것.

2차원 배열을, 1차원 배열로 접근하는 것이 핵심이었다.

애초에 arr을 1차원 배열로 구현했으면, 시간이 덜 걸렸겠지만, 코딩테스트였다면, 그걸 구현하는데 시간을 추가로 더 썼을 것 같다.

 

# 최종 코드 

import sys
from collections import deque
input = sys.stdin.readline

n, m, k = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))
    
def f(arr, k):
    start = 0
    end_row = n-1
    end_col = m-1

    while start < end_row and start < end_col:
        for _ in range(k%(2*(end_row+end_col-2*start))):
            q = deque()
            for i in range(start, end_row):
                q.append(arr[i][start])
            for i in range(start, end_col):
                q.append(arr[end_row][i])
            for i in range(end_row, start, -1):
                q.append(arr[i][end_col])
            for i in range(end_col, start, -1):
                q.append(arr[start][i])
                 
            #ㅜ
            for i in range(start, end_row):
                arr[i+1][start] = q.popleft()

            #ㅏ
            for i in range(start, end_col):    
                arr[end_row][i+1] = q.popleft()
                
            #ㅗ
            for i in range(end_row, start, -1):
                arr[i-1][end_col] = q.popleft()

            #ㅓ
            for i in range(end_col, start, -1):
                arr[start][i-1] = q.popleft()
                        
        start += 1
        end_row -= 1
        end_col -= 1

    return arr

arr = f(arr, k)
    
for a in arr:
    print(*a)

 

 

 

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

16927번: 배열 돌리기 2