[프로그래머스] 118670 - 행렬과 연산 (Python)

로고를 누르면 문제 페이지로 이동합니다.

---

 

문제 설명

직사각형 모양의 행렬이 있고, 모든 행이 한 칸씩 아래쪽으로 이동하는 ShiftRow 연산과 바깥쪽 원소들이 시계 방향으로 한 칸씩 이동하는 Rotate 연산이 있습니다.

ShiftRow 연산

Rotate 연산

주어진 연산들을 모두 수행한 뒤의 행렬 상태를 반환합니다.

 

제한사항

• 2 ≤ rc의 행 길이(=행렬의 가로 길이) ≤ 50,000
  • rc의 모든 행의 길이는 동일합니다.
• 2 ≤ rc의 열 길이(=행렬의 세로 길이) ≤ 50,000
  • rc의 모든 열의 길이는 동일합니다.
• 4 ≤ rc의 행 길이 x rc의 열 길이 ≤ 100,000
• rc[i][j] 는 i+1번째 행 j+1번째 열에 있는 원소를 나타냅니다.
  • 1 ≤ rc[i][j] ≤ 1,000,000
• 1 ≤ operations의 길이 ≤ 100,000
  • operations의 원소는 "ShiftRow" 혹은 "Rotate"입니다.

 

풀이

카카오 공식 블로그(링크)의 풀이를 참고했습니다.

첫 번째 풀이

아이디어

문제 그대로 연산을 구현한다면 ShiftRow 연산은 모든 원소를 움직여야 하기 때문에 N(행 수) * M(열 수) * Q(연산 수) 의 시간이 소요됩니다.

행렬의 행(N), 열(M) 길이의 최댓값은 각각 50,000 이하이고 연산의 최대 개수(Q)는 100,000 이기 때문에 효율성 테스트 케이스를 통과할 수 없습니다.

 

위 그림과 같이 행렬의 원소들을 행별로, 가장자리 원소들별로 관리한다면 두 연산의 시간복잡도는 다음과 같습니다.

 

ShiftRow 연산은 마지막(가장 아래) 행을 통째로 처음(가장 위)으로 옮기기 때문에 O(1)의 시간이 소요되고,

Rotate 연산은 바깥쪽 열 2줄과 행 2줄의 원소들 각각 1개씩만을 옮기기 때문에 역시 O(1)의 시간이 소요됩니다.

 

코드 (Python)

결과 (Python)