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

[문제]

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

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

 

[풀이]

문제에서 필요한 과정을 나누면 총 3가지로 나눌 수 있다.

1. rows x columns 크기 행렬 선언 후 1부터 rows x columns 까지의 숫자 대입
2. 행렬 테두리 회전하기
3. 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자를 순서대로 배열에 담기

1. rows x columns 크기 행렬 선언 후 1부터 rows x columns 까지의 숫자 대입

array = [[0 for col in range(columns)] for row in range(rows)]
value = 1
for row in range(rows):
    for col in range(columns):
        array[row][col] = value
        value += 1

위 코드 첫번째 줄을 통해 모든 값에 0이 초기화되어 있는 rows x columns 배열이 생성된다.

각 행과 열을 이중 for문을 통해 돌면서 값을 갱신해준다.

 

array = []
for row in range(rows):
    array.append([a for a in range(row * columns + 1, (row + 1) * columns + 1)])

찾아보니 위의 코드로 한번에 값까지 넣을 수 있지만 잘 이해가 되지 않아 첫 번째 코드를 사용했다.

 

2. 행렬 테두리 회전하기

for query in queries:    
        x1, y1, x2, y2 = query[0] - 1, query[1] - 1, query[2] - 1, query[3] - 1
        temp = array[x2][y2]

        # right
        for i in range(x2, x1, -1):
            array[i][y2] = array[i - 1][y2]
        # top
        for i in range(y2, y1, -1):
            array[x1][i] = array[x1][i - 1]
        # left
        for i in range(x1, x2):
            array[i][y1] = array[i + 1][y1]
        # bottom
        for i in range(y1, y2):
            array[x2][i] = array[x2][i + 1]
        array[x2][y2-1] = temp

queries는 이중 리스트로 구성되어 있기 때문에 반복문을 통해 각 테두리 부분의 숫자를 구한다.

 

오른쪽, 왼쪽, 위, 아래 각각 회전 규칙이 다르기 때문에 위치대로 나눠서 값을 갱신해주었다.

 

# 오른쪽

우선 사각형의 오른쪽부터 생각해보면 열 위치는 모두 동일하고 행의 위치만 변한다.

행의 숫자가 더 큰 위치가 그보다 한개 작은 행의 값을 가져와야 하기 때문에 반복문 범위를 역순으로 지정했다.

for i in range(x2, x1, -1):
	array[i][y2] = array[i - 1][y2]

 

 

 

옆의 그림을 예로 들자면 반복문이 4행부터 2행까지 역순으로 진행되는 것이다.

 

1. 4행 3열 <- 3행 3열

2. 3행 3열 <- 2행 3열

3. 2행 3열 <- 1행 3열

 

반복문을 통해 위처럼 새로운 값이 갱신된다.

 

 

 

 

 

# 위

사각형의 위인 경우에는 행 위치는 모두 동일하며 열의 위치만 변한다.

열의 숫자가 더 큰 위치가 그보다 한개 작은 열 값을 가져와야 하기 때문에 사각형의 오른쪽과 마찬가지로 반복문 범위를 역순으로 지정했다.

for i in range(y2, y1, -1):
    array[x1][i] = array[x1][i - 1]

 

 

 

 

 

이 경우는 반복문이 3열에서 2열까지 역순으로 진행된다.

 

1. 1행 3열 <- 1행 2열

2. 1행 2열 <- 1행 1열

 

 

 

 

 

 

 

# 왼쪽

사각형의 왼쪽인 경우 열 위치는 모두 동일하며 행의 위치만 변한다.

기준이 되는 행은 그보다 한개 큰 행 값을 가져와야 하기 때문에 반복문 범위는 순차로 지정했다.

for i in range(x1, x2):
    array[i][y1] = array[i + 1][y1]

 

 

 

 

 

반복문이 1행부터 3행까지 진행된다.

 

1. 1행 1열 <- 2행 1열

2. 2행 1열 <- 3행 1열

3. 3행 1열 <- 4행 1열

 

 

 

 

 

 

 

# 밑

사각형의 밑쪽의 경우 행 위치는 모두 동일하며 열의 위치만 변한다.

기준이 되는 열은 그보다 한개 큰 열 값을 가져와야 하기 때문에 반복문 범위는 순차로 지정했다.

for i in range(y1, y2):
    array[x2][i] = array[x2][i + 1]

 

반복문이 1열에서 2열까지 진행된다.

 

1. 4행 1열 <- 4행 2열

2. 4행 2열 <- 4행 3열

 

이 과정에서 문제가 하나 있는데 마지막으로 값을 변경한 4행 2열의 값은 28이여야 하는데, 이전에 사각형의 오른쪽 값을 변경할 때 갱신된 값인 22 로 변경된다.

 

따라서 사각형을 회전하기 전에 오른쪽 밑의 모서리 array[x][y]를 미리 temp 값에 저장해 둔 후 모든 반복문이 끝난 후 array[x][y-1]에 temp 값을 대입해주어야 한다.

 

 

 

3. 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자를 순서대로 배열에 담기

for query in queries:    
        x1, y1, x2, y2 = query[0] - 1, query[1] - 1, query[2] - 1, query[3] - 1
        temp = array[x2][y2]
        small = temp

        # right
        for i in range(x2, x1, -1):
            array[i][y2] = array[i - 1][y2]
            small = min(small, array[i][y2])
        # top
        for i in range(y2, y1, -1):
            array[x1][i] = array[x1][i - 1]
            small = min(small, array[x1][i])
        # left
        for i in range(x1, x2):
            array[i][y1] = array[i + 1][y1]
            small = min(small, array[i][y1])
        # bottom
        for i in range(y1, y2):
            array[x2][i] = array[x2][i + 1]
            small = min(small, array[x2][i])
        array[x2][y2-1] = temp
        
        answer.append(small)

사각형의 테두리 값에 접근할 때마다 미리 선언해두었던 small 변수와 값을 비교해 더 작은 값이 small에 갱신된다. 

 

 

[코드]

def solution(rows, columns, queries):
    array = [[0 for col in range(columns)] for row in range(rows)]
    value = 1
    for row in range(rows):
        for col in range(columns):
            array[row][col] = value
            value += 1
    
    answer = []
    for query in queries:    
        x1, y1, x2, y2 = query[0] - 1, query[1] - 1, query[2] - 1, query[3] - 1
        temp = array[x2][y2]
        small = temp

        # right
        for i in range(x2, x1, -1):
            array[i][y2] = array[i - 1][y2]
            small = min(small, array[i][y2])
        # top
        for i in range(y2, y1, -1):
            array[x1][i] = array[x1][i - 1]
            small = min(small, array[x1][i])
        # left
        for i in range(x1, x2):
            array[i][y1] = array[i + 1][y1]
            small = min(small, array[i][y1])
        # bottom
        for i in range(y1, y2):
            array[x2][i] = array[x2][i + 1]
            small = min(small, array[x2][i])
        array[x2][y2-1] = temp
        
        answer.append(small)
    return answer