[백준::1021번::Python] 회전하는 큐

의외로 굉장히 쉬운 문제다.

 

간단하게 말해서 큐의 시작과 끝을 이어붙인건데,

 

보통의 큐는 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

                        d a t a 1   d a t a 2    d a t a 3    d a t a 4

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

이렇다면 회전하는 큐는 다이얼전화기 같이 생겼다고 생각하면 된다.

 

문제에선 pop,left,right만 가능하다고 나와있다.

더 자세히 보면 뽑아내려는 n개의 수를 만나면 pop하고, 아니면 left혹은 right를 하는것인데

이건 엄청 간단하다. 현재 인덱스를 0번으로 고정하고, 목표 값이 있는 인덱스가 총 길이의 절반보다 크냐작냐에 따라 다르게하면 된다.

 

예로들어 1 2 3 4 5 6 7 8 9 10 가 있을때 2 9 5면,

1을 왼쪽으로 보내 2 3 4 5 6 7 8 9 10 1 이 될것이고

2를 pop한다. 이떄까지 왼쪽으로 한번갔다.

현재 : 3 4 5 6 7 8 9 10 1

이후 9의 위치를 보면 값들을 오른쪽으로 돌리면 되겠다는 판단이 선다.

9번이 있는 인덱스 값은 7이고 총 길이 9의 절반이 넘으니, 오른쪽으로 돌린다는 뜻이다.

그러면 1 3 4 5 6 7 8 9 10 -> 10 1 3 4 5 6 7 8 9 -> 9 10 1 3 4 5 6 7 8 9

여기서 9를 pop

현재 : 10 1 3 4 5 6 7 8

이제 5의 위치를 찾아야한다. 총 길이 8, 5의 위치는 4번 즉 왼쪽,오른쪽 어디로 가든 똑같다.

하지만 큐의 기본 특성을 고려해야한다. 디폴트는 오름차순이니, 값을 올리는 왼쪽으로 돌려주면 된다.

 

좀 더 줄여보자면

필요한 변수는

1. 1~n까지 적혀있는 리스트

2. 목표 값이 들어있는 리스트 (예 : 2 9 5)

3. 움직인 횟수를 세는 변수

 

대충 이러하고

1번 리스트의 0번째 값이 2번리스트의 0번째 값과 같다면 3번 변수의 카운트를 증가시켜주고 1,2번 리스트 전부 해당 값을 remove해준다.

 

1번리스트의 어떠한 값의 위치가 총 길이 / 2보다  크다면, 오른쪽으로 돌리면 된다.

그게 아니면 왼쪽으로 돌리면 된다.

 

매우 간 ㅡ 단

 

 

코 드 주 의

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#1021 spin Queue

import sys


def main():
    nSize,nCount = map(int,sys.stdin.readline().split())
    roulette = [_ for _ in range(1,nSize+1)]
    pickList = list(map(int,sys.stdin.readline().split()))
    currentIndex = 0
    nResultMoveCount = 0
    destIndex = 0
    while True:
        if nCount < 1:
            break
        # 현재있는 위치 - 목표 위치 절대값
        if destIndex == 0:
            destIndex = pickList[0]
        if roulette[currentIndex] == pickList[0]:
            roulette.remove(roulette[currentIndex])
            pickList.remove(pickList[0])
            nCount-=1
            destIndex = 0
        elif roulette.index(destIndex) > int(len(roulette) / 2): #오른쪽으로 돌림
            temp = roulette.pop()
            roulette.insert(0,temp)
            nResultMoveCount+=1
        else:
            temp = roulette[currentIndex]
            roulette.remove(roulette[currentIndex])
            roulette.append(temp)
            nResultMoveCount+=1
    print(nResultMoveCount)



main()