[HackerRank]Matrix Layer Rotation

문제 링크입니다!

문제 이해

이번 문제는 이해하긴 쉽지만 implementation part에서 가장 어려운 문제입니다.

검색 없이 정말 오랫동안 고민하여 풀었습니다. 거의 하루 종일...ㅠ 걸렸습니다.

문제는 주어진 행렬의 r번의 회전 후에 행렬 값을 구하는 문제입니다.

 

INPUT

m: matrix의 행값

n: matrix의 열 값

r: 회전 횟수

matrix: matrix의 원소 값들

OUTPUT

r번 회전 후의 matrix의 값들

정리하면

조건 1. 행렬의 행과 열은 2 이상 300 이하이다.
조건 2. 회전 횟수 1 이상 10⁹ 이하 이다. 이 조건이 코드를 어렵게 만듭니다.
조건 3. 행과 열 값 중에 작은 값은 짝수이다. 이 조건은 있어서 다행?인 조건입니다.

이 조건 안 보고 풀다가 삽질했어요...

여기까지 문제에 대한 설명입니다.

다음은 문제 풀이에 도움이 되는 힌트?를 드리겠습니다.

스

포

방

지

.

.

.

.

.

.

.

.

.

문제 힌트

이 문제의 생각해야 할 경우는 조건 2입니다.

조건 2 때문에 r이 가장 큰 값을 가지면 행렬을 1번 회전하는 함수를 구현해도 시간이 너무 걸려서 TEST 9에서 FAIL을 가집니다.(참고로 TEST 9는 m, n, r 값이 300, 300, 999999999입니다.) 그래서 저는 어떻게 하면 r의 계산을 줄일 수 있을까 고민했습니다.

아래 제가 생각한 방법을 적었습니다. 보고 싶으신 분은 Drag 하세요!

원소의 기준으로 다시 자기 자리의 자리로 이동하면 굳이 회전을 할 필요가 없습니다. 예를 들어 a[i][j] 원소가 4번 이동하면 다시 자기 자리로 돌아온다면, r값으로 401 값이 들어오면 한 바퀴면 돌면 된다. 하지만 모든 원소가 값은 수를 가지고 있는 게 아니라서 각각의 수들이 어떤 조건에서 주기가 어떻게 바뀌는지 파악하면 주기로 나눈 나머지의 값만큼 회전시켜주면 합니다.

다음 생각해야 할 경우는 바로 행렬의 이동 조건을 찾는 것입니다. 행렬의 원소는 4가지의 방법으로 밖에 이동합니다. 상하좌우!입니다. 이 4개의 이동의 조건을 찾는 게 이 문제의 중요한 포인트입니다. 저는 최대한 그림을 그려서 규칙을 찾으려고 했습니다. 행값과 열 값이 다를 수 있지만 같은 경우인 쉬운 경우를 먼저 생각해서 풀어 보았습니다.

저는 많은 제출로 잘 작동하는지 확인하며 풀었습니다. 디버그라고 하죠?

다음은 저의 코드를 올리면서 마치겠습니다.

스

포

방

지

.

.

.

.

.

.

.

.

.

참고로 저는 파이썬을 이용하여 풀었습니다.

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'matrixRotation' function below.
#
# The function accepts following parameters:
#  1. 2D_INTEGER_ARRAY matrix
#  2. INTEGER r
#
def printmatrix(m, matrix):
    for i in range(m):
        for j in matrix[i]:
            print(j, end=' ')
        print('')


def matrixRotation(m, n, matrix, r):
    # Write your code here
    check = 2*n + 2*m - 4

    mat = matrix
    i = 0
    while(check > 0 and i < min(n, m)//2):
        times = r % check
        for _ in range(times):
            a = mat[i][i]
            b = mat[m-1-i][i]
            c = mat[m-1-i][n-1-i]
            d = mat[i][n-1-i]
            for j in range(1,n-2*i):
                mat[i][j+i-1] = mat[i][j+i]
            for j in range(n-2*i-1,0,-1):
                mat[m-i-1][j+i] = mat[m-i-1][j+i-1]
            for j in range(m-1-2*i-1,0,-1):
                mat[i+j+1][i] = mat[i+j][i]
            for j in range(1,m-1-2*i):
                mat[i+j-1][n-1-i] = mat[i+j][n-1-i]
            mat[i+1][i] = a
            mat[m-1-i][i+1] = b
            mat[m-2-i][n-1-i] = c
            mat[i][n-2-i] = d

        i += 1
        check -= 8

    printmatrix(m, mat)

if __name__ == '__main__':
    first_multiple_input = input().rstrip().split()

    m = int(first_multiple_input[0])

    n = int(first_multiple_input[1])

    r = int(first_multiple_input[2])

    matrix = []

    for _ in range(m):
        matrix.append(list(map(int, input().rstrip().split())))

    matrixRotation(m, n, matrix, r)