밀기 알고리즘 -- 파이썬 데크(deque)

문제

길이가 m인 수열이 n개 존재한다. n, m, q와 이 수열들의 초기 상태가 0번 수열부터 n-1번 수열까지 순서대로 주어진다. 각 질문은 세 정수 f, x, y로 주어지는데, x가 1이면 f번 수열을 오른쪽으로 y칸 밀어낸 결과를, x가 2면 f번 수열을 왼쪽으로 y칸 밀어낸 결과를 출력하여라.

단, 각 수열의 모양은 다음 그림처럼 원형이라서 n-1번 인덱스의 다음 칸은 0번이다. 각 질문에 의해 밀린 수열은 원래대로 복구하지 않는다. 즉, 같은 수열을 여러 번 밀게 된다면 이전에 밀린 상태에서 추가로 밀어서 출력한다.

입력

첫 줄에 수열의 수 n과 수열의 길이 m, 질문의 수 q가 주어진다.

두 번째 줄부터 n개의 줄에 걸쳐 각 수열을 구성하는 수 m개가 주어진다.

세 번째 줄부터 q개의 줄에 걸쳐 f, x, y가 주어진다.

(3 ≤ n, m ≤ 1,000, 1 ≤ q ≤ 100, 0 ≤ f ≤ n-1, 1 ≤ 수열을 구성하는 수, y ≤ m, 1 ≤ x ≤ 2)

출력

q줄에 각 질문에 대한 답을 출력한다.

입력의 예

4 5 3

2 3 1 5 4

1 3 5 4 2

4 5 1 2 3

1 3 5 2 4

0 1 2

0 2 1

1 2 3

출력의 예

5 4 2 3 1

4 2 3 1 5

4 2 1 3 5

 

#코드(시간복잡도에서 걸린다.. )

n, m, q = map(int, input().split())
getInfo = [list(map(int, input().split())) for _ in range(n)]
qList = [list(map(int, input().split())) for _ in range(q)]
result = list()
 
# 세 정수 f, x, y
# x가 1이면 f번 수열을 오른쪽으로 y칸 밀어낸 결과 ==> 정방향
# x가 2면 f번 수열을 왼쪽으로 y칸 밀어낸 결과 ==> 역방향
# 0(행) 1(방향) 2(칸수)
def push(x, f):
  global getInfo
  if x == 1: # 정방향
    temp = getInfo[f][-1] 
    for i in range(m-1, 0, -1): 
      getInfo[f][i] = getInfo[f][i-1]
    getInfo[f][0] = temp  
    
  elif x == 2: # 역방향
    temp = getInfo[f][0]
    for i in range(1, m):
      getInfo[f][i-1] = getInfo[f][i]
    getInfo[f][-1] = temp
 
for i in range(q):
  f = qList[i][0]
  x = qList[i][1]
  y = qList[i][2]
  for j in range(y):
    push(x, f)
  
  for j in range(m):
    print(getInfo[f][j], end=' ')
  print()

#개선된 코드

import sys
from collections import deque
def pushmethod(f,x,y):
    global matrix
    idx_r=f
    dq_row=deque(matrix[idx_r])
    if(x==1):
        dq_row.rotate(y)
    else:
        dq_row.rotate(-y)
    matrix[idx_r]=list(dq_row)
    print(' '.join(map(str, matrix[idx_r])))
    
if __name__=="__main__":
    n,m,q = map(int, sys.stdin.readline().split())
    matrix=[]
    for _ in range(n):
        row=list(map(int, sys.stdin.readline().split()))
        matrix.append(row)
    cmds=[]
    for _ in range(q):
        cmd=list(map(int, sys.stdin.readline().split()))
        cmds.append(cmd)
    for cmd in cmds:
        f,x,y=cmd
        pushmethod(f,x,y)
    # for row in matrix:
    #     print(' '.join(map(str, row)))

 

#복습

import sys
from collections import deque
# 길이가 m인 수열이 n개 존재한다
# n, m, q와 이 수열들의 초기 상태가 0번 수열부터 n-1번 수열까지 순서대로 주어진다
# 각 질문은 세 정수 f, x, y로 주어지는데, 
# x가 1이면 f번 수열을 오른쪽으로 y칸 밀어낸 결과를,
# x가 2면   f번 수열을 왼쪽으로   y칸 밀어낸 결과를 출력
 
def push(f, x, y):
  global frame
  
  if x == 1:
    deq = deque(frame[f])
    deq.rotate(y)
  if x == 2:
    deq = deque(frame[f])
    temp = y * (-1)
    deq.rotate(temp)
  frame[f] = deq
  for i in frame[f]:
    print(i, end=' ')
  print()
 
if __name__ == "__main__":
  input = sys.stdin.readline
  n, m, q = map(int, input().split())
  frame = [ list(map(int, input().split())) for _ in range(n) ]
  
  for _ in range(q):
    f, x, y = map(int, input().split())
    push(f, x, y)

 

- 간략히 파이썬 데크에대해 정리...

Deque in Python

Deque (Doubly Ended Queue) in Python is implemented using the module “collections“. Deque is preferred over list in the cases where we need quicker append and pop operations from both the ends of container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity.

 

보통 큐(queue)는 선입선출(FIFO) 방식으로 작동한다. 반면, 양방향 큐가 있는데 그것이 바로 데크(deque)다.

즉, 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.

데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.

컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.

 

데크(deque) 사용법

데크는 다음처럼 임포트(import)해 사용한다.

from collections import deque
 
deq = deque()
 
# Add element to the start
deq.appendleft(10)
 
# Add element to the end
deq.append(0)
 
# Pop element from the start
deq.popleft()
 
# Pop element from the end
deq.pop()

데크(deque)에 존재하는 메서드(method)는 대략 다음과 같다.

• deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
• deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
• deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
• deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.
• deque.remove(item): item을 데크에서 찾아 삭제한다.
• deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

여기서 rotate() 메서드(method)가 특히 재밌는데, 설명이 부족하니 코드를 추가해 보겠다.

# Contain 1, 2, 3, 4, 5 in deq
deq = deque([1, 2, 3, 4, 5])
 
deq.rotate(1)
print(deq)
# deque([5, 1, 2, 3, 4])
 
deq.rotate(-1)
print(deq)
# deque([1, 2, 3, 4, 5])

이렇게 양수 값 또는 음수 값을 파라미터(parameter)로 제공하여 데크(deque)를 좌, 우로 회전할 수 있다.

데크(deque), 언제, 왜 써야 하는가?

요약하자면, 데크(deque)는 스택처럼 사용할 수도 있고, 큐 처럼 사용할 수도 있다.

시작점의 값을 넣고 빼거나, 끝 점의 값을 넣고 빼는 데 최적화된 연산 속도를 제공한다.

즉, 대부분의 경우에 데크(deque)는 리스트(list)보다 월등한 옵션이다.

데크는 특히 push/pop 연산이 빈번한 알고리즘에서 리스트보다 월등한 속도를 자랑한다.

 

출처 : 

https://www.geeksforgeeks.org/deque-in-python/

Deque in Python - GeeksforGeeks

https://chaewonkong.github.io/posts/python-deque.html

Python - 데크(deque) 언제, 왜 사용해야 하는가?