백준 - 1021 회전하는 큐

deque의 메소드 중 하나인 .rotata()를 이용하면 된다.

1번 연산은 첫번째 요소를 pop하므로 popleft연산이므로 일반 queue가 아닌 deque를 사용해야 한다.
2번 연산은 왼쪽으로 한 칸 씩 이동 즉, 왼쪽으로 회전하므로 rotate(음수) 또한
3번 연산은 오른쪽으로 한 칸 씩 이동 즉, 오른쪽 회전하므로 rotate(양수)이다.

2 9 5 <- 각 K를 의미한다.
2를 popleft하기 위해서는 두 가지 방법이 있다.
왼쪽으로 1번 rotate 시켜야한다  = rotate(-(2-1)) 
오른쪽으로 9번 rotate 시켜야한다 = roata(10-(2-1))

2,3번 연산의 최소 횟수 이므로 최소한의 회전을 찾아야 하므로 min을 이용한다.


해당 요소를 popleft한 후에는 deque의 길이가 9로 줄어든다.

또한 2를 popleft하기 위해서 회전이 일어났으므로 deque의 상태는 처음 상태와는 다르다. 왼쪽으로 한번 회전하고 2를 popleft했으므로 deque의 처음 원소는 3번째 원소이다(편의상 3이라고 함) 

3에서 부터 9를 popleft하기 위해서는 두 가지 방법이 있다.
왼쪽으로 6번 rotate 시켜야한다  = rotate(-(9-3))
오른쪽으로 3번 rotate 시켜야한다 = roata(9-(9-3))

즉 , K번째 요소를 얻기 위해서 K-deque[0](오른쪽 회전), K-(K-deque[0])(왼쪽 회전) 중 더 작은 값을 가진 방향으로 회전하면 된다.
K값이 더 작으면 음수로 무조건 양수보다 작기 때문에 절대값으로 비교한다~~~~
=>rotate(min( abs(K-deque[0]),abs(K-(K-deque[0])) ) )

9를 popleft했으므로 dequeue의 길이는 8이다. 이 때 첫번째 요소는 10이다.

10에서 부터 5를 popleft하기 위해서는 두 가지 방법이 있다.
왼쪽으로 5번 rotate 시켜야한다  = rotate(-(5-10))
오른쪽으로 3번 rotate 시켜야한다 = roata(8-(5-10)) ==> ??

라고 생각했는데 막상 해보니까 아니다...

이 문제의 idea는 ...

왼쪽, 오른쪽 회전 중 더 작은 값을 찾는 것이다.

이 값을 찾기 위해서는 빼내려는 요소의 index값을 알아야 한다. 이때 deque.index()를 이용해서 해당 요소의 index값을 알 수 있다.

즉 deque.index(2 , 5 , 9)를 통해서 현재 index를 얻어와 deque[0]에서 가까운 쪽으로 회전하는 것이다.

index()를 통해서 얻어온 요소의 index값을 K라 하자.

K는 첫번째 요소로 부터 떨어진 거리이다. 거꾸로 생각하면 deque의 끝에서 부터의 거리도 구할 수 있다. len(deque) - K이다.

즉 첫번째 요소로 부터 더 가까우면 왼쪽으로 회전, 끝에서 부터 더 가까우면 오른쪽 회전하면 된다.