[deque, 덱] 백준 1021번 회전하는 큐 c++ 풀이

BOJ 1021번 회전하는 큐 c++ 풀이

• 랭크 : 실버4
• 백준 1021번 회전하는 큐
  
  
  

문제 정리

1. N개의 원소를 포함하고 있는 양방향 순환 큐가 있다.
2. 첫 번째 원소를 뽑아낸다.
3. 왼쪽으로 한 칸 이동. a1..ak -> a2..ak, a1
4. 오른쪽으로 한 칸 이동 a1...ak -> ak, a1...ak-1
5. 뽑아내려고 하는 원소의 위치가 주어질 때, 원소를 주어진 순서대로 뽑아내는데 필요한 4,5번 연산의 최솟값을 구하여라
   
   
   

문제 접근

1. arr의 idx 번째 수를 맨 앞에 나오게 만들어야 합니다. 그래야 pop해서 순서를 만들 수 있습니다.
2. 최소의 연산을 하기 위해서는 왼쪽으로 움직여서 맨 앞으로 가져오느 경우, 오른쪽으로 움직여서 맨 앞으로 가져오는 경우 모두 해보아야 합니다.
3. 그래서 왼쪽으로 움직여서 idx 번째 수를 맨 앞으로 가져오는 경우 몇 번 움직이는지??
4. 오른쪽으로 움직여서 가져오는 경우 몇 번 움직이는지 체크하여 더 작은 경우로 움직여서 pop합니다.
   
   
   

문제 풀이

1. pop 해야 할 순서를 arr 배열에 저장합니다.
2. deque에 1부터 N까지의 수를 넣어놓습니다.
3. 우선 왼쪽으로 이동시켜 봅니다. 맨 앞에 원하는 수가 왔다면 멈추고, 그렇지 않다면 temp deque에 저장하여 shift 시켜봅니다.
4. 그렇게 왼쪽으로 몇 번 이동시켜야 하는지 left 변수에 저장하고 다시 원상복구 시킵니다.
5. 오른쪽도 마찬가지로 진행합니다.
6. 그리고 더 작은 이동 횟수를 가지는 방법으로 이동시키고 해당 숫자를 pop합니다.
7. 이를 모든 수를 정상적으로 출력할때까지 반복합니다.
8. 그리고 누적된 이동 횟수를 출력합니다.
   
   
   

백준 1021 회전하는 큐 c++ 코드

 

풀이 인증