행렬 테두리 회전하기

 

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

프로그래머스

문제풀이

디버깅을 하는 게 중심적인 문제이다.

각 테두리의 요소들에 회전을 어떻게 적용하는지가 중요한데 아래와 같이 코드를 작성하면 직관적으로 각 요소들이 제대로 변환이 되었는지 확인할 수가 있다.

 

아래 방법은 기존 배열을 복사하여 이전 값들의 요소를 그대로 가져와서 board를 업데이트하는 방법이다. 당시에는 아래와 같이 풀이를 진행했다.

 

# 디버깅용
# 아래 코드에 queries문에서 사용시 각 변에 회전을 적용 시켰을 때 제대로 변환 했는지 단계별로 한 눈에 확인 가능하다.
slice_board = [row[y1 : y2 + 1] for row in board[x1 : x2 + 1]]
print(slice_board)

def solution(rows, columns, queries):
    answer = []
    board = [[(j + 1) + (i * columns) for j in range(columns)] for i in range(rows)]
    for x1, y1, x2, y2 in queries:
        x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
        copy_board = [row[:] for row in board]
        min_value = float("inf")

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

 

 

위와 다르게 아래와 같이 기존 값을 temp에 저장 한 뒤 풀이를 한다면 시간 복잡도의 효율성을 챙길 수 있다만 rows, columns의 크기는 최대 100, queries의 크기는 최대 10000 이기 때문에 코드가 하나 더 추가된다고 해서 유의미한 차이는 생기지 않기에 빠르게 풀이 방법을 증명할 수 있는 방법을 택하는 게 편하다.

def solution(rows, columns, queries):
    answer = []
    board = [[(j + 1) + (i * columns) for j in range(columns)] for i in range(rows)]
    for x1, y1, x2, y2 in queries:
        x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
        min_value = float("inf")
        temp = board[x1][y1]
        min_value = min(min_value, temp)

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