[백준] 회전하는 큐 1021

문제

큐에서 세가지 연산을 수행할 수 있다.
1. 첫번째 원소를 뽑아낸다.
2. 큐를 왼쪽으로 한 칸 이동시킨다. (원순열처럼 이동)
3. 큐를 오른쪽으로 한 칸 이동시킨다.

큐에 처음에 포함되어 있던 수 N과 뽑아내려는 원소의 위치가 주어질 때 주어진 원소를 순서대로 뽑아내는데 드는 2,3번 연산의 최솟값을 출력하시오.

입력

큐의 크기 : N, 뽑아내려고 하는 수의 개수 :M
N은 50보다 작거나 같은 자연수
M은 N보다 작거나 같은 자연수
위치는 1보다 크거나 같고, N보다 작거나 같은 자연수

풀이

예시 입력
10 3
1 2 3
예시 출력
0

1. n개의 수를 덱에 넣는다.
2. 뽑아내려고 하는 개수 m만큼 while문을 돌린다.
3. 입력받은 수가 front에 가까운지 back에 가까운지 계산한다.
4. front에 가까우면 L으로 이동하는 연산
5. back에 가까우면 R로 이동하는 연산
6. 연산을 할 때마다 연산 개수를 ans++한다.

위의 과정을 다시 정리하면
1. 뽑으려는 수가 front, back 중 어느쪽에 더 가까운지 판단
2. 이동 횟수가 적은 방향으로 pop push 진행
3. 이동할 때마다 ans++
이렇게 세가지 단계로 나눌 수 있다.

1번 과정을 어떻게 하지..?
만약 9 10 1 2 3 4 5 6 7 8 일 때 1을 뽑고 싶다면
9-1 = 8, 8-1 = 7 이렇게 계산할수도 없다.

그럼 front back 둘다 연산을 한 후 연산 개수로 비교하는 방법으로 풀어야겠다!
1. 뽑으려는 수가 front, back 중 어느쪽에 더 가까운지 판단
A. 뽑으려는 수를 l이동으로 뽑을 때 걸리는 cnt
B. 뽑으려는 수를 r이동으로 뽑을 때 걸리는 cnt
C. 둘의 수 비교
2. 이동 횟수가 적은 방향으로 pop push 진행
3. 이동할 때마다 ans++

풀이1

1. 뽑으려는 수가 front, back 중 어느쪽에 더 가까운지 판단
   A. 뽑으려는 수를 l이동으로 뽑을 때 걸리는 cnt
   B. 뽑으려는 수를 r이동으로 뽑을 때 걸리는 cnt
   C. 둘의 수 비교

아니 근데 왜 두번째 예제 답이 8임??
6아니야??

1 2 3 4 5 6 7 8 9 10 cnt =0
2 3 4 5 6 7 8 9 10 1 cnt =1
3 4 5 6 7 8 9 10 1 pop =1
1 3 4 5 6 7 8 9 10 cnt =2
10 1 3 4 5 6 7 8 9 cnt =3
10 1 3 4 5 6 7 8 pop =2
8 10 1 3 4 5 6 7 cnt =4
7 8 10 1 3 4 5 6 cnt =5
6 7 8 10 1 3 4 5 cnt =6
6 7 8 10 1 3 4 pop =3
cnt =6, pop=3

미미미치겠다.
1번 연산을 보면 "첫번째 원소를" 뽑아낸다고 적혀있다.
ㅋㅋㅋ.....ㅋㅋ..ㅋ

양방향 큐이지만 뒤에서는 뽑아낼 수 없다. 아니 이런
문제를 꼼꼼히 읽자 한시간 헤맸네

이거는 망한 풀이 -> l, r 이동 cnt 모두 구하려고 했는데 그러면 l하고 나면 덱에서 순서가 바뀌기 때문에 덱을 두개 만들어야 하는 불편함이 있음 -> 버려

#include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0);
    cin.tie(0);
  
    int n;
    int m;
    cin >>n; //1
    cin >> m; //1
    int ans=0;
    
    deque<int> D;
    for(int i=1; i<=n; i++) D.push_back(i); //1
    
    while(m--){
        int num;
        cin >> num;
        int cnt_L=0, cnt_R=0;
        
        //왼쪽 이동
        while(num != D.front() && D.size()>1){
            if(num == D.front()) D.pop_front(); break;
            D.push_back(D.front());
            D.pop_front();
            cnt_L++;
        }
        
        //오른쪽 이동
        while(num != D.back() && D.size()>1){
            if(num == D.back()) D.pop_back(); break;
            D.push_front(D.back());
            D.pop_back();
            cnt_R++;
        }
        ans += min(cnt_L, cnt_R);
        
    }
    
    cout << ans;
    
    
    
    
    return 0;
}

풀이 2 - 덱 안의 원소의 위치 사용 find(시작점, 끝점, 찾는 원소)

#include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0);
    cin.tie(0);
  
    int n;
    int m;
    cin >>n; //1
    cin >> m; //1
    int ans=0;
    
    deque<int> D;
    
    for(int i=1; i<=n; i++) D.push_back(i); //1
    
    while(m--){
        int num;
        cin >> num;
        
        int idx = find(D.begin(), D.end(), num) - D.begin(); //idx: num이 있는 위치
    
        while(D.front() != num){ //front에서만 뽑을 수 있음!!
            //왼쪽에 더 가까우면
            if(idx < D.size()-idx){ //2번 < 10-2 = 8
                D.push_back(D.front()); 
                D.pop_front();
            }
            //오른쪽에 더 가깝거나 중간이면
            else{
                D.push_front(D.back());
                D.pop_back();
            }
            ans++;
        }
        D.pop_front();
    }
    
    cout << ans;
    
    
    
    
    return 0;
}