백준 1021번 회전하는 큐

문제 링크입니다: https://www.acmicpc.net/problem/1021

왼쪽으로 쉬프트하는 경우와 오른쪽으로 쉬프트하는 경우 모두 존재하기 때문에 이를 쉽게 구현할 수 있는 덱(deque)을 사용하여 문제를 풀었습니다.

알고리즘은 아래와 같습니다.

1. 1~N까지 덱에다 집어넣고 뽑아내고자 하는 수의 위치를 iterator를 통해 찾습니다.

2. 찾은 위치를 통해 좌우로 쉬프트하는 경우 중 어떤 경우가 유리한지를 찾아내고 유리한 쪽으로 쉬프트를 진행합니다.

#include <iostream>

#include <deque>

#include <algorithm>

using namespace std;

 

int N, M;

deque<int> dq;

 

int main(void)

{

        cin >> N >> M;

 

        for (int i = 1; i <= N; i++)

                 dq.push_back(i);

 

        int result = 0;

        for (int i = 0; i < M; i++)

        {

                 int idx;

                 cin >> idx;

 

                 int cur = 1;

                 //뽑아내고자 하는 수의 위치

                 for (deque<int>::iterator iter = dq.begin(); iter < dq.end(); iter++)

                 {

                         if (*iter == idx)

                                 break;

                         cur++;

                 }

 

                 //왼쪽으로 몇 번 쉬프트?

                 int left = cur - 1;

                 //오른쪽으로 몇 번 쉬프트?

                 int right = dq.size() - cur + 1;

 

                 if (left < right)

                 {

                         for (int j = 1; j <= left; j++)

                         {

                                 int num = dq.front();

                                 dq.pop_front();

                                 dq.push_back(num);

                                 result++;

                         }

                         dq.pop_front();

                 }

                 else

                 {

                         for (int j = 1; j <= right; j++)

                         {

                                 int num = dq.back();

                                 dq.pop_back();

                                 dq.push_front(num);

                                 result++;

                         }

                         dq.pop_front();

                 }

        }

 

        cout << result << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~