[백준] 16927번: 배열 돌리기 2- 파이썬 (+구현 알고리즘)

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

16927번: 배열 돌리기 2

문제

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

A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
   ↓                                       ↑
A[2][1]   A[2][2] ← A[2][3] ← A[2][4]   A[2][5]
   ↓         ↓                   ↑         ↑
A[3][1]   A[3][2] → A[3][3] → A[3][4]   A[3][5]
   ↓                                       ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]

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

1 2 3 4       2 3 4 8       3 4 8 6
5 6 7 8       1 7 7 6       2 7 8 2
9 8 7 6   →   5 6 8 2   →   1 7 6 3
5 4 3 2       9 5 4 3       5 9 5 4
 <시작>         <회전1>        <회전2>

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

 

입력

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

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

 

출력

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

 

풀이

그냥 구현문제로 열심히 쳐다보면서 작성했다. 

처음에는 회전수가 10^9보다 작다는 제한을 보고 회전되는 모든 고리의 크기로부터 최소공배수를 구해 그 만큼 전체를 회전하려고 했다.

BUT! 전체가 아닌 고리마다 회전시킬 때 회전수를 고리의 크기로 나눈 후 돌리는게 더 효율적이며 시간 초과가 안났다!

 

구현문제
=
풀이를 떠올리는 것은 쉽지만 코드로 옮기기 어려운 문제

사실 구현문제는 특별한 알고리즘 기법은 필요없는 정확한 풀이가 핵심이라고 한다.

 

구현문제를 푸는 팁을 찾아봤는데, 구현문제 흐름을 보니

문제를 해결할 수 있는 방식을 생각해보고, 과정을 세분화해서 작성하고 어려운 점은 구글링을 통해 학습하면 좋을 것이라고 했다.

 

답안 코드

import math

N, M, R = map(int, input().split())

NUMBERS = [list(map(int, input().split())) for _ in range(N)]

#### ㅇ페ㅏㄹ오ㅔ라 오페라랄라랄라 아름다운 아리아~

turns = []
for k in range(min(N, M)//2):
    turns.append(2*((N-(2*k))+(M-(2*k)))-4)


for k in range(min(N,M)//2):
    for r in range(R%turns[k]):
        temp = NUMBERS[k][k]
        for i in range(1+k, M-k):
            NUMBERS[k][i-1] = NUMBERS[k][i]

        for i in range(1+k, N-k):
            NUMBERS[i-1][M-1-k] = NUMBERS[i][M-1-k]

        for i in range(1+k, M-k):
            NUMBERS[N-1-k][M-i]=NUMBERS[N-1-k][M-1-i]

        for i in range(1+k, N-k):
            NUMBERS[N-i][k] = NUMBERS[N-1-i][k]

        NUMBERS[1+k][k] = temp

for n in NUMBERS:
    print(" ".join(map(str,n)))

시간초과와 싸운 흔적

 

++) 면접 스터디 멤버 YG님이 추천해주신 노래에 중독되서 아무생각 없이 듣다가 풀렸다! (김장훈- 오페라)