[프로그래머스] 행렬 테두리 회전하기
알고리즘/문제풀이

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

문제가 그렇게 어려웠던 문제는 아니었다. 근데, 정말 오래걸렸다. 단순 구현문제라고 해서 답지를 보면 안된다길래 안보고 풀었지만.. 시간도 오래걸리고 ㅠㅠ 또르르...

일단 dx, dy를 코딩테스트로 풀때 우리가 생각하는 2차원 평면상의 x, y좌표랑 너무 헷갈렸다. 실제 문제풀때 이런게 헷갈리면 안돼서 이부분을 좀 제대로 머리에 인식해둬야겠다는 생각이 들었다.

그리고, 인덱스가 헷갈리는 문제는 꼭 종이에 풀이하면서, 변수명을 정확히 적으면서 해야한다.

1. 문제 설명


row와 columns가 주어지고, 주어진 만큼 1부터 시작해서 행렬을 채워 넣는다.
이후 문제에서 2,2 와 5,4 사이의 원소를 회전시키라고 한다.


회전시키면 이러한 형태가 된다.
이렇게 회전시킬 좌표를 n개가 문제에서 주어진다. 그리고, 회전시킬때마다 회전을 하는 원소들 중 가장 작은 숫자를 리턴하면 된다.

위의 예시에서는 8이 가장 작은 원소가 되겠다.

2. 어려웠던 점

1) 회전후의 테이블로 업데이트 후 다시 회전

회전할때마다 원소들은 옆으로 이동하거나 위로 이동하기 때문에 옆으로 이동하면 열 값이 1커지거나 작아지고, 아래로 이동하면 board의 행 길이만큼 커지거나 작아진다고 생각했다. 하지만 이렇게 풀면 안된다. 왜냐면, 회전하면 중간 원소들의 값이 달라지기 때문에 증감하는 숫자의 크기도 달라진다.

그래서 그냥 진짜 교체를 해줘야 한다.

2) dy, dx 헷갈림

이런문제가 나오면 고등학교때 풀었던 좌표평면이 자꾸 떠올라서 헷갈린다. 일단 프로그래밍 배열에서 2차원 배열이라고 하면, 가장 0번째 오는 원소는 dy가 된다. 왜냐면 행번호이기 때문이다. 그리고 1번째 원소는 dx가 된다 왜냐면, 옆으로 이동한다.
그림으로 이해하는게 더 빨라서 아래 그림을 꼭 기억해두자.

그래서 dy는 y에 추가할 증가량 즉 행에 추가할 원소이다. 따라서 dy가 코드상 더 앞쪽에 나오는게 맥락상 자연스럽다.
dx는 x에 추가할 증가량 즉 열에 추가할 원소이다. 따라서 dx는 뒤쪽에 나온다.

3. 풀이

그대로 구현하면 된다. 아이디어를 조금 설명하자면 다음과 같다.

1) 아이디어

회전한다는 것이 결국 교체하는 것과 다를게 없다. 예를들어 다음과 같은 빨간색으로 표시된 숫자를 시계방향으로 이동시키면, 다음과 같다.


이러한 이동은 4가지 부분으로 나뉘어 진다.

  • 열 이동

  • 행 이동

이 4가지 사진의 경우를 코드로 구현하면 된다. 어려운 것은 아니다. 매우 헷갈림

2) 코드

나는 이렇게 풀이했다.

 

from collections import deque


def rotate(board, x1, y1, x2, y2):
    temp = deque()
    # 추출
    for dx in range(0, x2 - x1):
        temp.append(board[y1 - 1][(x1 - 1) + dx])  # 위줄 첫번째 부터 n-1번째까지
        temp.append(board[y2 - 1][(x1 - 1) + dx + 1])  # 아래줄 두번째부터 n번째까지

    for dy in range(0, y2 - y1):
        temp.append(board[(y1 - 1) + dy + 1][x1 - 1])  # 첫번째 열에서 두번째부터 n번째까지
        temp.append(board[(y1 - 1) + dy][x2 - 1])  # 마지막 열에서 첫번째부터 n-1번째까지

    min_score = min(temp)

    # 추출된 원소 차례대로 삽입
    for change_dx in range(1, x2 - x1 + 1):
        board[y1 - 1][x1 - 1 + change_dx] = temp.popleft()  # 위줄 두번째부터 n번째까지로 바꿈
        board[y2 - 1][x1 - 1 + change_dx - 1] = temp.popleft()  # 아래줄 첫번째부터 n-1번째까지로 바꿈

    for change_dy in range(1, y2 - y1 + 1):
        board[(y1 - 1) + change_dy - 1][x1 - 1] = temp.popleft() # 첫번째 열에서 첫번째부터 n-1번째까지 삽입
        board[(y1 - 1) + change_dy][x2 - 1] = temp.popleft() # 마지막 열에서 두번째부터 n번째까지 삽입

    return min_score, board


def solution(rows, columns, queries):
    result = []
    board = [[x + (y - 1) * columns for x in range(1, columns + 1)] for y in range(1, rows + 1)]

    for i in queries:
        y1, x1 = i[0], i[1]
        y2, x2 = i[2], i[3]

        min, board = rotate(board, x1, y1, x2, y2)

        result.append(min)

    return result