프로그래머스 - 행렬과 연산

이 문제는 초기 행렬 rc와 ShiftRow, Rotate로 이루어진 operations가 주어지면 행렬 연산을 해서 결과를 출력하는 문제다.
먼저 ShiftRow는 아래로 한줄씩 밀어내는 연산으로 rc = rc[-1] + rc[:-1]라고 표현할 수 있다.
그 다음 Rotate 연산은 바깥쪽 테두리의 값들이 시계방향으로 한칸씩 이동하는 것으로 다음과 같이 표현할 수 있다.

• 윗줄 = rc[1][0] + rc[0][:-1]

• 오른줄 = rc[1:][-1] = rc[:-1][-1]

• 밑줄 = rc[-1][:-1] = rc[-1][1:]

• 왼줄 = rc[1:-1][0] = rc[2:][0]

• 예시
  1 2 3 -> 4 1 2
  4 5 6 -> 7 5 3
  7 8 9 -> 8 9 6

첫번째 풀이

먼저 위에 정의한 내용을 그대로 코드로 구현했다. 여기서 약간 헤맸던 부분은 이중행렬을 copy할 시에, 내부 리스트의 요소들은 copy가 안되고 같은 메모리를 사용해서 같이 변경이 된다는 것이었다. 그래서 전에 정리해놨던 얕은 복사와 깊은 복사에 대한 글을 참고하여 deepcopy를 시도했더니 되었다.
아래 코드는 정확성 테스트는 모두 통과했지만, 효율성 테스트에서 막혔다.

import copy 
def rotate(rc):
    height = len(rc)
    width = len(rc[0])
    new_rc = copy.deepcopy(rc)
    # 윗줄
    new_rc[0] = rc[1][:1] + rc[0][:-1]
    # 오른쪽 줄
    for i in range(1, height):
        new_rc[i][-1] = rc[i-1][-1]
    # 아랫줄 
    for i in range(width-1):
        new_rc[-1][i] = rc[-1][i+1]
    # 왼쪽 줄
    for i in range(1, height-1):
        new_rc[i][0] = rc[i+1][0]
    return new_rc

def solution(rc, operations):
    for op in operations:
        if op == 'ShiftRow':
            new_rc = rc[-1:] + rc[:-1]
            rc = new_rc
        elif op == 'Rotate':
            rc = rotate(rc)
    return rc

두번째 풀이

제한사항을 다시 살펴보니 주어지는 행렬의 크기도, 연산의 길이도 매우 컸다.

• 2 ≤ rc의 행 길이(=행렬의 가로 길이) ≤ 50,000
  rc의 모든 행의 길이는 동일합니다.
• 2 ≤ rc의 열 길이(=행렬의 세로 길이) ≤ 50,000
  rc의 모든 열의 길이는 동일합니다.
• 4 ≤ rc의 행 길이 x rc의 열 길이 ≤ 100,000
• 1 ≤ operations의 길이 ≤ 100,000
  최악의 경우 2x50000이 될 수 있을 것이다. 그럼 행렬 자체를 deque으로 처리해보면 어떨까?

from collections import deque

def solution(rc, operations):
    height = len(rc)
    width = len(rc[0])
    left_col = deque([rc[i][0] for i in range(height)])
    right_col = deque([rc[i][width - 1] for i in range(height)])
    rows = deque([deque(rc[i][1:width - 1]) for i in range(height)])

    for op in operations:
        if op == 'ShiftRow':
            left_col.appendleft(left_col.pop())
            rows.appendleft(rows.pop())
            right_col.appendleft(right_col.pop())
        else:  # 'Rotate'
            rows[0].appendleft(left_col.popleft())
            right_col.appendleft(rows[0].pop())
            rows[height - 1].append(right_col.pop())
            left_col.append(rows[height - 1].popleft())
    answer = []
    for i in range(height):
        answer.append([left_col[i]] + list(rows[i]) + [right_col[i]])
    return answer

deque의 중첩 deque는 한번도 생각해보지 못한 구조였다. 결국 카카오 해설을 참고하여 풀었는데, 앞으로는 제한사항을 먼저 확인해서 풀이 방향을 정하는 연습을 해야할 것 같다.