문제 링크
풀이 과정
•
직관적인 방식으로는, 각 명령어(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
Python
복사
유사 문제
특정 원소를 다른 위치에 옮겨야 하는 상황에 시간 복잡도 이슈로 직관적인 풀이가 불가능 한 경우가 있습니다.
이럴 때는, 크게 다음과 같이 접근할 수 있습니다.
•
다른 자료구조를 사용하여 문제를 접근
•
실제로 원소를 이동 시키지 않고 인덱스를 이용하여 문제를 접근
이러한 관점에서, 제가 생각한 유사 문제는 아래와 같습니다!
•
특정 원소를 다른 위치에 옮겨야 하는 상황에 시간 복잡도 이슈로 직관적인 풀이가 불가능 한 경우가 있습니다.
이럴 때는, 크게 다음과 같이 접근할 수 있습니다.
•
다른 자료구조를 사용하여 문제를 접근
•
실제로 원소를 이동 시키지 않고 인덱스를 이용하여 문제를 접근
이러한 관점에서, 제가 생각한 유사 문제는 아래와 같습니다!
•