16926 - python

문제

제한조건

시간제한 1초

입출력 예

내 풀이

• N * M 행렬에서 테두리수는 min(n,m)//2개가 된다
  현재 좌표를 (x,y)라 하고, 다음 좌표(nx,ny)와 계속 swap하는 방식으로 구현하였다.
  
• 이 식은 i번째 테두리에 있는 원소의 개수가 2N + 2M - (8i-4)에서 나온식으로 방향전환을 하는 것을 고려한 횟수로 for문을 돌렸다
• 각 테두리에서 꼭짓점으로 만나게 되는 좌표가 어떻게 되나 생각해보았을 때
  제일 처음은 0 ~ n, 0 ~ m
  다음은 1 ~ i-1, 1 ~ m-1
  이런 관계를 형성하게 되어서 꼭짓점을 만나기 전까진 다음좌표와 swap하는데
  꼭짓점을 만나게 되면 방향을 전환하게 한다.

그러나, 시간초과 발생
n = 300 , m = 300 , r = 1000 인 경우를 생각하면 1초가 넘게된다.

다른 사람 풀이

from collections import deque


def rotate_board(r):
    global N, M, board
    q = deque()
    _width, _height = M, N
    time = min(_width, _height) // 2
    nx, ny = 0, 0

    while time >= 1:
        for i in range(_width-1):
            q.append(board[ny][nx+i])
        for i in range(_height-1):
            q.append(board[ny+i][nx+_width-1])
        for i in range(_width-1):
            q.append(board[ny+_height-1][nx+_width-1-i])
        for i in range(_height-1):
            q.append(board[ny+_height-1-i][nx])

        q.rotate(-r)

        for i in range(_width-1):
            board[ny][nx+i] = q.popleft()
        for i in range(_height-1):
            board[ny+i][nx+_width-1] = q.popleft()
        for i in range(_width-1):
            board[ny+_height-1][nx+_width-1-i] = q.popleft()
        for i in range(_height-1):
            board[ny+_height-1-i][nx] = q.popleft()

        _width -= 2
        _height -= 2
        nx += 1
        ny += 1
        time = min(_width, _height) // 2


N, M, R = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
rotate_board(R)
for i in range(N):
    print(*board[i])

이 블로그 참고
deque이랑 deque내장함수 rotate를 사용함