알고리즘 코드카타 112 - 행렬 테두리 회전하기

https://school.programmers.co.kr/learn/courses/30/lessons/77485

프로그래머스

문제 설명
rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.
다음은 6 x 6 크기 행렬의 예시입니다.

6 * 6 행렬

이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.

회전을 적용

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항
rows는 2 이상 100 이하인 자연수입니다.
columns는 2 이상 100 이하인 자연수입니다.
처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
모든 회전은 순서대로 이루어집니다.
예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

 

방법자체는 바로 떠오르지 않았지만 Numpy라이브러리를 활용하면 편할것같다는 생각이 들었다. 

import numpy as np

def solution(rows, columns, queries):
    answer = []
    matrix = np.arange(1, rows * columns + 1).reshape(rows, columns)
    
    return print(matrix)

 

먼저 numpy를 import한 뒤에 rows * columns 행렬을 생성하고 1부터 rows * columns까지 값으로 채워 넣었다.

 

for query in queries:
        x_1 = query[0] - 1
        x_2 = query[2]
        y_1 = query[1] - 1
        y_2 = query[3]
        sub_matrix = matrix[x_1:x_2, y_1:y_2]
        print(sub_matrix)

 

그 다음으로는 회전시키려는 부분 행렬의 위치를 반환한다. 이제 sub_matrix를 시계방향으로 회전시켜서 원래 행렬인 matrix에 반영하면 된다.

 

def rotate_matrix(matrix):
    rows, cols = matrix.shape
    r_matrix = np.copy(matrix)
    
    r_matrix[0, 1:cols] = matrix[0, 0:cols-1]
    r_matrix[1:rows, cols-1] = matrix[0:rows-1, cols-1]
    r_matrix[rows-1, 0:cols-1] = matrix[rows-1, 1:cols]
    r_matrix[0:rows-1, 0] = matrix[1:rows, 0]
    
    return r_matrix

 

넘파이 배열의 테두리를 회전시키는 함수를 작성했다.

배열을 복사해서 회전할 배열을 만들어주고 위에서 부터 순서대로 배열을 이동시켜서 값을 대체한다.

1. 가장 위의 행의 원소들을 회전시킨다.

2. 가장 오른쪽의 열의 원소들을 회전시킨다.

3. 가장 아래의 행의 원소들을 회전시킨다.

4. 가장 왼쪽의 열의 원소들을 회전시킨다.

 

for query in queries:
        x_1 = query[0] - 1
        x_2 = query[2]
        y_1 = query[1] - 1
        y_2 = query[3]
        sub_matrix = matrix[x_1:x_2, y_1:y_2]
        sub_matrix = rotate_matrix(sub_matrix)
        matrix[x_1:x_2, y_1:y_2] = sub_matrix

 

회전시킨 배열을 원래 배열에 적용을 해줘서 목표 배열을 작성한다.

 

for query in queries:
        x_1 = query[0] - 1
        x_2 = query[2]
        y_1 = query[1] - 1
        y_2 = query[3]
        sub_matrix = matrix[x_1:x_2, y_1:y_2]
        sub_matrix = rotate_matrix(sub_matrix)
        matrix[x_1:x_2, y_1:y_2] = sub_matrix
        answer.append(int(np.min(sub_matrix)))

 

마지막으로 회전시킨 배열에서 가장 작은 숫자를 찾아서 answer에 넣어주면 된다.

실패!

 

테스트케이스는 통과했지만 정답은 맞추지 못했다... 여러 질문들을 검색해본 결과 회전시키는 배열이 아니라 그 안에 있는 배열까지 고려되어 최소값이 구해졌기 때문에 에러가 발생한것같다.

 

def rotate_matrix(matrix):
    rows, cols = matrix.shape
    r_matrix = np.copy(matrix)
    temp = []
    
    r_matrix[0, 1:cols] = matrix[0, 0:cols-1]
    for i in r_matrix[0, 1:cols]:
        temp.append(i)
    
    r_matrix[1:rows, cols-1] = matrix[0:rows-1, cols-1]
    for i in r_matrix[1:rows, cols-1]:
        temp.append(i)
    
    r_matrix[rows-1, 0:cols-1] = matrix[rows-1, 1:cols]
    for i in r_matrix[rows-1, 0:cols-1]:
        temp.append(i)
    
    r_matrix[0:rows-1, 0] = matrix[1:rows, 0]
    for i in r_matrix[0:rows-1, 0]:
        temp.append(i)
    
    return r_matrix, min(temp)

 

배열을 회전시키는 함수를 수정해주었다. 회전시키는 원소들을 따로 저장한 후에 최소값을 구해서 함께 반환하도록 한다.

 

import numpy as np

def rotate_matrix(matrix):
    rows, cols = matrix.shape
    r_matrix = np.copy(matrix)
    temp = []
    
    r_matrix[0, 1:cols] = matrix[0, 0:cols-1]
    for i in r_matrix[0, 1:cols]:
        temp.append(i)
    
    r_matrix[1:rows, cols-1] = matrix[0:rows-1, cols-1]
    for i in r_matrix[1:rows, cols-1]:
        temp.append(i)
    
    r_matrix[rows-1, 0:cols-1] = matrix[rows-1, 1:cols]
    for i in r_matrix[rows-1, 0:cols-1]:
        temp.append(i)
    
    r_matrix[0:rows-1, 0] = matrix[1:rows, 0]
    for i in r_matrix[0:rows-1, 0]:
        temp.append(i)
    
    return r_matrix, min(temp)

def solution(rows, columns, queries):
    answer = []
    matrix = np.arange(1, rows * columns + 1).reshape(rows, columns)
    
    for query in queries:
        x_1 = query[0] - 1
        x_2 = query[2]
        y_1 = query[1] - 1
        y_2 = query[3]
        sub_matrix = matrix[x_1:x_2, y_1:y_2]
        sub_matrix, min_matrix = rotate_matrix(sub_matrix)
        matrix[x_1:x_2, y_1:y_2] = sub_matrix
        answer.append(int(min_matrix))
    
    return answer

이번에는 성공!

 

성공은 했지만 검색해서 찾아보니 코딩테스트 문제를 풀때는 외부라이브러리 사용을 하지 않는 것이 좋다고 한다. 더 심한경우에는 내부 라이브러리를 사용하지 못하는 경우도 있다고 하니 numpy는 당연히 사용할 수 없다고 생각하는 것이 좋을것같다. 종종 내부라이브러리를 사용하는 경우도 있는데 불가피한 상황이 아니라면 그런 것들도 줄여나가야할것같다.