1021번 - 회전하는 큐

💡 문제 이해를 잘하자..ㅎ😅

<처음 코드

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int,input().split(' '))
position = deque(map(int,input().split(' ')))

dq = deque(i+1 for i in range(N))
cnt = 0

while position:
    
    if dq[0] == position[0]:
        dq.popleft()
        position.popleft()
    elif len(dq) - dq.index(position[0]) > dq.index(position[0]):
        dq.append(dq.popleft())
        cnt += 1
    else:
        dq.appendleft(dq.pop())
        cnt += 1
    
print(cnt)

• 이 문제의 풀이는 사실 그렇게 어렵지는 않았던 거 같다.
• 음.. 다만 문제가 바로 이해가 안되어서 계속 헤맸던 거 같다...ㅎ
• 일단 풀이의 논점은 "현재 위치(가장 앞부분)과 내가 찾으려고 하는 index까지가 "앞에서 가는것이 가까운지" or "뒤에서 가는것이 가까운지"를 판단해야 했다.
• 따라서, List와 동일하게 deque에도 해당 값의 Index를 반환해주는 "index()"를 활용해서, 내가 찾으려 하는 것의 index가 앞에서 가까울 때와 뒤에서 가까울 때를 조건으로 나눠서 풀이하였다.

<수정 코드>

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int,input().split(' '))
position = deque(map(int,input().split(' ')))

dq = deque(i+1 for i in range(N))
cnt = 0

while position:
    
    if dq[0] == position[0]:
        dq.popleft()
        position.popleft()
        # 전체 크기를 매번 세지 않기 위해 추가한 코드
        N -= 1
	# 전체 크기를 매번 세지 않기 위해 수정한 코드
    elif N  > 2 * dq.index(position[0]):
        dq.append(dq.popleft())
        cnt += 1
    else:
        dq.appendleft(dq.pop())
        cnt += 1
    
print(cnt)

• 이거는 코드를 짜고 나서 생각이 들었던건데, len(dq)를 하게 되면 결국, 매번 dq을 전체 순환을 해야하기 때문에,크기를 저장해두고, pop()을 할 경우에 -1 하도록 설정하여서, 시간 복잡도를 줄일 수 있었다.
• 또한 크기를 계속 적으로 N으로 지정하면서 "N - dq.index(position[0]) > dq.index(position[0])" 이 부분을 "N > 2 * dq.index(position[0])" 이런 방식으로 전부 넘겨서 수정하였다.
  => 사실 이 방식은 시간복잡도에는 차이는 없으나, 뭐.. 코드가 짧아지긴 했으니.. 만족이다..ㅎ

• 뿌듯하게도 len함수를 변수로 바꾼것이 동작 시간을 조금이지만 줄여 주었다!!

💡 코테 스터디 중 나온 기발한 풀이법

• 혜진님: "N > 2 * dq.index(position[0]):" 이 부분을 len(dq)/2 로 선언해서 절반을 기준으로 어디에 더 가까운지 진행하였습니다.

• ⭐️ 서현님: "rotate()" 메소드를 사용하여, 부호가 - 이면, 그 갯수만큼 pop()해서 appendleft()를 해주고, 부호가 + 이면, 그 갯수만큼 popleft()해서 append()를 해주는 식으로 코드를 단축하였습니다.