[프로그래머스] 행렬 테두리 회전하기 - 파이썬
2023.1.7. 최초 작성
Lv2.
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/77485?language=python3
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.
x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.
다음은 6 x 6 크기 행렬의 예시입니다.
이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.
행렬의 세로 길이(행 개수) 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입니다.
- 모든 회전은 순서대로 이루어집니다.
- 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.
입출력 예
| rows | columns | queries | result |
| 6 | 6 | [[2,2,5,4],[3,3,6,6],[5,1,6,3]] | [8, 10, 25] |
| 3 | 3 | [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] | [1, 1, 5, 3] |
| 100 | 97 | [[1,1,100,97]] | [1] |
입출력 예 설명
입출력 예 #1
회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.
입출력 예 #2
회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.
입출력 예 #3
이 예시에서는 행렬의 테두리에 위치한 모든 칸들이 움직입니다. 따라서, 행렬의 테두리에 있는 수 중 가장 작은 숫자인 1이 바로 답이 됩니다.
[문제분석]
전체 행렬에서 입력받은 좌표에 해당하는 행렬의 테두리만 회전 후 해당 테두리에서 최솟값을 구하는 문제이다.
전체 행렬의 값 변화를 실제로 변경하지 않고 최솟값만 구하는 것이 가능할지 검토해보았지만 불가능하다고 판단하였다. 서로 다른 테두리 회전을 여러 번 진행되어야 하고 이전 회전이 다음 회전에 영향을 주기 때문이다.
문제에서 행렬의 시작 번지는 1을 기준으로 하였다. 그러나 구현할 때 사용할 리스트 자료구조는 시작 번지가 0에서 시작되므로 입력받은 좌푯값에 1을 빼고 사용하기로 한다.
한꺼번에 모든 것을 만드는 것보다 기능별로 분리하여 함수로 구현하는 것이 좋다.
[접근 방법]
문제 해결의 순서는 다음과 같고 별도의 함수로 만들어 진행한다.
1. rows와 columns을 입력받아 행렬을 만들고 1부터 증가하는 값을 대입한다.
2. 입력받은 회전할 테두리 좌표(왼쪽 위, 오른쪽 아래) 정보로 테두리의 좌푯값 정보를 만든다. 리스트를 2개 만들어 같은 번지를 기준으로 대입하도록 한다.
이렇게 2개의 리스트를 만들어 회전할 좌푯값을 관리할 때 좋은 점은 복잡하게 계산할 필요 없다는 것이다.
3. 회전할 테두리 좌푯값 정보로 실제 행렬의 값을 변경하고 이동한 값 중 최솟값을 구한다.
회전할 테두리의 좌표는 테두리가 시계방향으로 회전하므로 좌푯값은 시계 반대 방향으로 확보하는 것이 좋다.
행렬 테두리를 회전시킨다는 것은 값이 덮어써지게 되므로 기준이 되는 첫 번지의 값은 별도로 백업해둬야 한다.
[풀이 코드]
행렬을 2차원 리스트로 만들며 초기화하는 코드이다.
setBoard는 solution함수에서 호출하며 rows와 columns는 채점 시스템이 입력해주는 데이터로 행렬 정보이고 board는 전체 행렬을 관리하기 위해 만든 리스트이다.
테두리 좌푯값을 구하는 함수이다. 테두리는 왼쪽 위를 기준으로 시계 반대 방향으로 리스트에 저장한 후 반환한다.
입력된 회전할 행렬은 (y1, x1), (y2, x2)로 정의하였고 리스트의 0번지부터 사용하기 위해 –1씩 처리한다.
테두리 회전 함수이다. 테두리 좌푯값에 해당하는 값들을 시계방향으로 이동하고 최솟값을 반환한다.
solution 함수이다. 위의 함수들을 호출하여 흐름을 제어하고 최종적으로 최솟값 리스트를 만들어 반환한다.
[정리]
행렬의 2차원 리스트를 만들어 좌푯값을 잘 사용해야 하는 문제이다. 특히 회전을 어떻게 구현할지가 중요한데 불필요한 작업을 최소화하고 기능의 모듈화를 통해 함수로 만들어 사용하는 것을 권장한다.
문제를 작은 조각으로 분리하고 분리된 것을 함수로 구현하며 차분히 한 스텝씩 밟아가면 크게 헷갈리지 않고 풀어갈 수 있다. 그런데 문제를 분리하지 않고 한 번에 큰 덩어리로 풀어가려면 테두리 좌푯값을 회전하는 부분에서 많이 헷갈릴 수 있는 문제이다.