행렬 테두리 회전하기

11214 단어 구현구현

프로그래머스

영역의 테두리 숫자만 한칸씩 시계방향으로 회전. 이 때 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 반환

  • 행렬에는 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부터 하나씩 증가하면서 적혀있습니다.
  • queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
  • queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.

입출력

rowscolumnsqueriesresult
66[[2,2,5,4],[3,3,6,6],[5,1,6,3]][8, 10, 25]
33[[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]][1, 1, 5, 3]
10097[[1,1,100,97]][1]


접근 방식

행렬을 만들고 4가지 부분으로 나누어 회전. 제일 왼쪽 위 숫자를 기준으로 잡는다. 부분을 회전할 때마다 최솟값을 구해 저장한다.

  • 회전시키기 위해서는 기준이 되는 빈 칸이 하나 있어야 한다.
  • 왼쪽 상단을 기준으로 잡고, 회전은 시계 방향으로 진행되므로 왼쪽 끝을 올리고 맨 밑 줄을 왼쪽으로 옮기고 오른쪽 끝을 내리고 맨 윗 줄을 오른쪽으로 밀어준다.
    (⬆ ⬅ ⬇ ➡ 순서대로 진행)
  • 마지막으로 기준이 되었던 수를 있어야 할 곳에 돌려놓는다.
  • 회전을 시키면서 동시에 값을 비교하며 최솟값을 찾는다.
  • 받는애 입장에서 생각


코드

def solution(rows, columns, queries):
    
    matrix = [[0]*columns for _ in range(rows)]
    k = 1
    for i in range(rows):
        for j in range(columns):
            matrix[i][j] = k
            k += 1
            
    ans = []
    for x1, y1, x2, y2 in queries:
        a = matrix[x1-1][y1-1]
        v = a
        
        # 위로
        for x in range(x1-1, x2-1):
            matrix[x][y1-1] = matrix[x+1][y1-1]
            v = min(v, matrix[x][y1-1]) 
            
        # 왼쪽으로
        for y in range(y1-1, y2-1):
            matrix[x2-1][y] = matrix[x2-1][y+1]
            v = min(v, matrix[x2-1][y]) 
        
        # 아래로
        for x in range(x2-1, x1-1, -1):
            matrix[x][y2-1] = matrix[x-1][y2-1]
            v = min(v, matrix[x][y2-1]) 
        
        # 오른쪽으로
        for y in range(y2-1, y1-1, -1):
            matrix[x1-1][y] = matrix[x1-1][y-1]
            v = min(v, matrix[x1-1][y]) 
        
        matrix[x1-1][y1] = a
        ans.append(v)
        
    return ans

좋은 웹페이지 즐겨찾기