백준 1021번 - 회전하는 큐

https://www.acmicpc.net/problem/1021

이 문제는 해당 위치에 있는 원소가 첫 번째 원소가 되기 위해 몇 번을 움직여야 하는지를 알아야 한다.


여기서 나는 문제에 주어진 위치를 숫자라고 생각했다.


문제에 제시된 N이 10 일 때
1,2,3,4,5,6,7,8,9,10이라는 원소가 있다고 생각하고
주어진 원소의 위치를 해당 위치에 있는 원소 값이라고 생각했다.
(해당 원소의 위치 = 해당 원소의 위치에 해당하는 값)



예를 들어 문제에 제시된 것처럼
뽑아내려는 원소가 3개 있고 각각의 처음 위치는 1,2,3일 때


1,2,3,4,5,6,7,8,9,10에서 1번 위치를 선별하면
2,3,4,5,6,7,8,9,10으로 바뀐다.


그다음에 처음 원소의 2 번 위치가 어디 있는지를 알기 위해서는
2라는 값 자체가 어디 있는지를 알면 되는 것이다.




첫 번째 원소부터 각각의 원소 순서인 sequence가 0부터 시작한다고 할 때
왼쪽으로 움직이는 경우는  해당 원소의 sequence 값 자체가 왼쪽으로 움직이는 횟수가 된다.
반대로 오른쪽으로 움직일 때는 전체 배열의 사이즈에서 sequence를 뺀 값이 된다.


예를들어 1,2,3, 4 ,5,6,7,8,9,10에서 4라는 값을 기준으로 왼쪽과 오른쪽으로 움직일 때
왼쪽은 원소 값 4의 sequence인 3만큼 움직이면 되고
오른쪽은 10-sequence인 7만큼 움직이면 첫 번째 원소로 이동한다.



마지막으로 실수했던 부분은 어떤 방향으로 움직이든 sequence를 기준으로 오른쪽에 모든 원소를 정렬하고 

그다음에 왼쪽에 있는 모든 원소를 정렬하면 해당 위치에 존재하는 원소를 선별하고 움직인 위치가 된다.


오른쪽으로 움직일 때 선별 후 정렬되는 원소를 sequence를 기준으로 왼쪽이 정렬되고 오른쪽이 정렬된다고 생각했다. 

무의식적으로 왼쪽으로 움직일 때를 기준으로 반대로 생각했다.


그러나 어떤 방향으로 움직이든 정렬되는 값 자체는 같고 단지 몇 번 움직이냐의 차이가 있다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    
    int N,M;
    cin>>N>>M;
    
    vector<int> vec; //1부터 N까지의 숫자
    for(int i=1;i<=N;i++)
        vec.push_back(i);
    
    
    vector<int> location(M,0);
    for(int i=0;i<M;i++){
        scanf("%d",&location[i]);
    }
    
    int ans=0;
    for(int i=0;i<M;i++){
        
        int sequence=0;
        for(;sequence<vec.size();sequence++)
            if(vec[sequence]==location[i])
                break;
        
        
        int left_move=sequence; //왼쪽으로 회전할 때
        int right_move=(int)vec.size()-sequence; //오른쪽으로 회전할 때
        ans+=min(left_move,right_move);
        
        vector<int> vec2;
       
        for(int i=sequence+1;i<vec.size();i++)
            vec2.push_back(vec[i]);
        
        for(int i=0;i<sequence;i++)
            vec2.push_back(vec[i]);
        
        vec=vec2;
    }
    
    
    cout<<ans<<endl;
    return 0;
}