백준 1021번 회전하는 큐 (Python 문제풀이)

---

백준 1021번 회전하는 큐

 

풀이법

시간 제한이 2초로 매우 넉넉하기 때문에 시간에 대한 고려없이 단순하게 덱 사용해서 rotate 시키면 되는문제다.

 

 

코드

방향을 향해 1번씩 Rotate해서 찾으면 pop하는 코드

import sys
from collections import deque

N,M=map(int,sys.stdin.readline().rstrip().split(" "))
targetLi =list(map(int,sys.stdin.readline().rstrip().split(" ")))
dq = deque([i for i in range(1,N+1)])

nowCount = 0

for target in targetLi:
    while(True):
        if(dq[0]==target): 
            dq.popleft()
            break
        else:
            if(dq.index(target) <= len(dq)//2):
                dq.rotate(-1)
                nowCount+=1
            else:
                dq.rotate(1)
                nowCount+=1
print(nowCount)

 

방향까지 거리를 측정해서 한번에 rotate하는 코드

import sys
from collections import deque

N,M=map(int,sys.stdin.readline().rstrip().split(" "))
targetLi =list(map(int,sys.stdin.readline().rstrip().split(" ")))
dq = deque([i for i in range(1,N+1)])

nowCount = 0

for target in targetLi:
    idx = dq.index(target) 
    if idx <= len(dq)//2:
        nowCount += idx
        dq.rotate(-idx)
    else:
        nowCount += len(dq) - idx
        dq.rotate(len(dq)-idx)
    dq.popleft()  
print(nowCount)

 

 

 

2번째 코드가 더 빨라보이지만 시간상 차이는 거의 없다.;; rotate(n)이 rotate(1)을 n번 불러오는거와의 시간차이는 호출오버헤드의 차이정도밖에 없는듯하다