[프로그래머스/PYTHON] 행렬 테두리 회전하기

문제 링크

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

코딩테스트 연습 - 행렬 테두리 회전하기

---

● 문제 설명

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

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

행렬의 세로 길이(행 개수) 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입니다.
  • 모든 회전은 순서대로 이루어집니다.
  • 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

---

● 문제 해결 방향

처음 생각한 방법은 n*m개의 숫자를 좌표로 표시하여 좌표를 통해 결과 값을 출력하려 했다.

실패 후, 단순한 2차원 배열을 생성하여, 주어진 쿼리로 4개의 범위에 대해 각각 숫자를 조작하는 방법을 사용.

---

● 문제 해결 코드

 

처음 짠 코드는 다음과 같다.

def solution(rows, columns, queries):
    answer = []
    matrix = {}
    k = 1
    for i in range(rows):
        for j in range(columns):
            matrix[k] = [i + 1, j + 1]
            k += 1
    
    for q in queries :
        minimum = rows * columns + 1
        for i in range(1, rows * columns + 1):
            if (matrix[i][0] >= q[0] and matrix[i][0] <= q[2]) and (matrix[i][1] >= q[1] and matrix[i][1] <= q[3]) and not ((matrix[i][0] >= q[0]+1 and matrix[i][0] <= q[2] - 1) and (matrix[i][1] >= q[1] + 1 and matrix[i][1] <= q[3] - 1)):
                if minimum > i:
                    minimum = i

                if matrix[i][0] == q[0]:
                    if matrix[i][1] == q[3]:
                        matrix[i] = [matrix[i][0] + 1, matrix[i][1]]
                    else :
                        matrix[i] = [matrix[i][0], matrix[i][1] + 1]

                elif matrix[i][0] == q[2]:
                    if matrix[i][1] == q[1]:
                        matrix[i] = [matrix[i][0] - 1, matrix[i][1]]
                    else :
                        matrix[i] = [matrix[i][0], matrix[i][1] - 1]

                elif (matrix[i][0] >= q[0] and matrix[i][0] <= q[2]) and matrix[i][1] == q[1]:
                    matrix[i] = [matrix[i][0] - 1, matrix[i][1]]

                elif (matrix[i][0] >= q[0] and matrix[i][0] <= q[2]) and matrix[i][1] == q[3]:
                    matrix[i] = [matrix[i][0] + 1, matrix[i][1]]
                    
        answer.append(minimum)
    print(answer)
    return answer

처음 짜본 코드는

n * m 개의 숫자에 좌표를 부여한 dict를 선언하여

 

1부터 n*m까지 반복하면서 쿼리가 제시한 영역의 숫자이면 그 연산을 처리해주도록 코드를 짰다.

 

하지만 1 부터 끝까지 반복해야 하다 보니 몇 가지 테스트 케이스에서 런타임 에러가 떴고,

쿼리에서 제시한 영역으로 만 반복문을 돌리려다보니 코드가 복잡해져 다른 방법을 사용하였다.

 

def solution(rows, columns, queries):
    answer = []
    matrix = {}
    k = 1
    for i in range(rows):
        for j in range(columns):
            matrix[k] = [i + 1, j + 1]
            k += 1
    
    for t, l, b, r in queries :
        minimum = t*columns + l
        
        for n in range((t - 1)*columns + l, (t - 1)*columns + r):
            matrix[n] = [matrix[n][0] + 1, matrix[n][1]]
            minimum = min(minimum, n)
            
        for n in range((b - 1)*columns + r, (b - 1)*columns + l, -1):
            matrix[n] = [matrix[n][0] - 1, matrix[n][1]]
            minimum = min(minimum, n)

        for n in range(t, b):
            v = n*columns + l
            matrix[v] = [matrix[v][0] - 1, matrix[v][1]]
            minimum = min(minimum, v)

        for n in range(b, t, -1):
            v = n*columns + r
            minimum = min(minimum, v)   
            
        answer.append(minimum)
    return answer

다른 분들의 코드도 일부 참고하여 비슷한 코드를 만들었다.

먼저 2차원 배열을 만들어 n*m 개의 숫자를 넣고,

 

쿼리로 만들 수 있는 4가지 범위에 해당하는 숫자를

각각 적절한 연산을 수행하도록 for문을 여러개 배치하였다.

---

● 알게 된 것 / 아쉬운 점