큐와 덱, 1021번 회전하는 큐 풀이

회전하는 큐 문제를 시도해보았다는 전제하에 문제풀이를 설명하도록 하겠습니다.

문제의 핵심은 원하는 숫자를 빼내는 최적의 횟수를 구하는 것입니다.

최적의 횟수, 조건을 파악하는 것이 매우 중요합니다.

예시를 기반으로 생각해 보았을 때

10 2

2 9

위와 같은 입력이 주어졌을 때

2는 인덱스 1에 위치합니다. 이때는 왼쪽으로 한 칸씩 이동하는 것이 가장 빠르게 2를 빼내는 경로입니다.

리스트는 1~10에서 3,4,5,6,7,8,9,10,1이 됩니다. 이때의 9의 인덱스는 6입니다.

이 때는 오른쪽으로 3번 이동하는 것이 최적의 경로입니다.

답은 5입니다.

위의 예시를 기반으로 생각했을 때 빼내고자 하는 숫자의 인덱스가 리스트의 중간 인덱스보다 클 때는 오른쪽으로 이동해서 빼고 작을 때는 왼쪽으로 이동해 빼내야 합니다.

답은 아래 코드입니다.

아래 코드보다 훨씬 효율적인 코드들이 있으니 다른 분들의 풀이도 반드시 확인해보세요.

저는 항상 문제를 풀고 1등의 풀이를 봅니다.

이번에도 보았는데 기본적인 로직은 같습니다.

하지만 if/else 구문없이 풀 수 있더라고요. 

그 풀이도 확인해보세요

 

def RotatingQueue(n,k):
    nlist=[i for i in range(1,n+1)]
    klist=[int(i) for i in input().split()]
    r=0
    for i in klist:
        indi=nlist.index(i)
        if indi>(n//2):
            r+=(n-indi)
        else:
            r+=indi
        n-=1
        nlist=nlist[indi+1:]+nlist[:indi]
    return(r)

n,k=map(int, input().split())
print(RotatingQueue(n,k))