문제 링크

풀이 과정

• 직관적인 방식으로는, 각 명령어(operation)마다 이중 리스트를 순회하면서 Rotate 또는 ShiftRow 연산을 수행하면 됩니다.
• 이렇게 문제를 접근하면, 정확성 테스트는 통과할 수 있지만 시간 초과로 인하여 효율성 테스트는 통과할 수 없습니다.
• 따라서, 이중 리스트의 원소를 효율적으로 이동시키는 방법을 생각해야합니다.
• 먼저 ShiftRow 연산은 간단하게 처리할 수 있을 것 같습니다.
  • 굳이 모든 행을 이동시킬 필요 없이, 마지막 행을 첫 번째 행에 위치시키면 됩니다.
  • 이는 한 개의 **큐(deque)**를 사용하면 O(1)의 시간 복잡도로 처리할 수 있습니다.
• 하지만, Rotate 연산은 첫번째 행/마지막 행/첫번째 열/마지막 열의 원소를 동시에 이동시켜야 하므로, 한 개의 큐로 처리할 수 없습니다.
• 그렇다면 큐의 장점을 살리면서 Rotate 연산을 처리할 수 있을까요?
• 큐의 갯수를 조금 늘려서, 3개의 큐를 사용해봅시다.
  • left: 첫 번째 열에 있는 원소를 저장
  • mid: 두 번째부터 (n-1)열에 있는 원소를 저장
  • right: 마지막 n열에 있는 원소를 저장
• mid에는 행 단위로 큐(deque)를 삽입하는 것이 핵심입니다!
  • append(), pop() 연산의 시간 복잡도를 O(1)로 수행하기 위함입니다.
  • Rotate 연산 시, 첫 번째 행과 마지막 행만 영향을 받게 됨을 주목하세요!
• Rotate 연산은 아래 네 번의 연산을 통해 O(1)의 시간 복잡도로 해결이 가능합니다.
  • left의 첫 번째 원소는 mid에 있는 첫 번째 큐의 첫 번째 위치로 이동합니다.
  • mid에 있는 첫 번째 큐의 마지막 원소는 right의 첫 번째 위치로 이동합니다.
  • right에 있는 마지막 원소는 mid에 있는 마지막 큐의 마지막 위치로 이동합니다.
  • mid에 있는 마지막 큐의 첫 번째 원소는 left의 마지막 위치로 이동합니다.

전체 코드

from collections import deque

def solution(rc, operations):
    answer = []
    left, mid, right = deque(), deque(), deque()
    for element in rc:
        left.append(element[0])
        # append(), pop() 연산의 시간 복잡도를 O(1)로 수행하기 위하여, deque 자료형을 append합니다!
        mid.append(deque(element[1:-1]))
        right.append(element[-1])
        
    for operation in operations:
        if operation == 'ShiftRow':
            left.appendleft(left.pop())
            mid.appendleft(mid.pop())
            right.appendleft(right.pop())
        else:
            mid[0].appendleft(left.popleft())
            right.appendleft(mid[0].pop())
            mid[-1].append(right.pop())
            left.append(mid[-1].popleft())
            
    while left:
        answer.append([left.popleft()] + list(mid.popleft()) + [right.popleft()])
        
    return answer

유사 문제

특정 원소를 다른 위치에 옮겨야 하는 상황에 시간 복잡도 이슈로 직관적인 풀이가 불가능 한 경우가 있습니다.

이럴 때는, 크게 다음과 같이 접근할 수 있습니다.

• 다른 자료구조를 사용하여 문제를 접근
• 실제로 원소를 이동 시키지 않고 인덱스를 이용하여 문제를 접근