[algorithm] 백준 1021번 회전하는 큐

 

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

int main() {
    int n,m,x;
    cin >> n >> m;
    int cnt=0;
    vector<int> v2;
    deque<int> d;
    for(int tmp=1; tmp<n+1; tmp++) d.push_back(tmp);
    for(int tmp=0; tmp<m; tmp++)
        {
            cin >> x;
            v2.push_back(x);
        }

    for(int tmp : v2)
        {
            int count = 1;
            for(int tmp2 : d)
                {
                    if(tmp2 == tmp) break;
                    else count++;
                }

            while(1)
                {
                    if(d.front() == tmp)
                    {
                        d.pop_front();
                        break;
                    }

                    if(d.size()%2 == 0) // 짝수크기일 때
                    {
                        if(count <= (d.size()/2))
                        {
                            d.push_back(d.front());
                            d.pop_front();
                            cnt++;
                        }
                        else
                        {
                            d.push_front(d.back());
                            d.pop_back();
                            cnt++;
                        }
                    }
                    else // 홀수일 때
                    {
                        if(count <= (d.size()/2)+1)
                        {
                            d.push_back(d.front());
                            d.pop_front();
                            cnt++;
                        }
                        else
                        {
                            d.push_front(d.back());
                            d.pop_back();
                            cnt++;
                        }
                    }
                    
                }            
        }
    cout << cnt;
    return 0;
}

 

우선 뽑아내려고 하는 수를 벡터에 넣고

1 ~ N까지의 원소를 가진 덱을 만든다

 

뽑아내려고 하는 수의 위치에 따라

2번 연산을 사용할 지 3번 연산을 사용할 지가 결정되므로

뽑아내려고 하는 수의 처음 위치를 count 변수로 지정한다

 

그 후 뽑아내려고 하는 수가 맨 앞에 올 때까지

2번 혹은 3번 연산을 반복해서 수행하는데

덱의 크기가 짝수일 때와 홀수일 때  가운데 쪽에 위치한 원소를

2번 연산쪽으로 처리할지 3번 연산쪽으로 처리할 지 나뉘므로 유의해서 구현해야한다

연산을 한 번 수행할 때마다 cnt 변수를 1씩 증가시켜

최종적으로 몇 번의 연산을 하였는 지 도출해낼 수 있다.

 

덱의 크기가 짝수일 때와 홀수일 때를 구분지어서 구현해야하는 부분에서

오류가 많았고 발상적인 실수도 많았던 것이 아쉬웠다

조금 더 차분히 생각하고 머릿속을 정리해가면서

발상을 떠올리고 구현해야할 것 같다.