[C++]백준 - 1021번 문제

1021번: 회전하는 큐 (acmicpc.net)

1021번: 회전하는 큐

 

1021번 : 회전하는 큐

---

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

 

 

출력

---

첫째 줄에 문제의 정답을 출력한다.

 

 

 

---

 

생각해 볼 점

---

문제에서 나온 것처럼, 양방향 큐인 덱을 쓰면 됩니다.

pop -> push 방향만 잘 정하면 왼쪽 순환, 오른쪽 순환이 가능합니다.

 

덱의 양쪽에서 목표 숫자를 찾고, 발견된 방향 쪽으로 순환시켜서 pop하도록 코드를 작성했습니다.

 

덱 : { 1, 2, 3, 4, 5 } 및 deque.end();

2를 찾는다면

 

0 회

앞 : 1

뒤 : deque.end() (pop은 앞에서 이루어지므로 뒤에서 찾는 경우 횟수를 1회 증가시킨 것입니다.)

 

1회

앞 : 2

뒤 : 5

 

1회에 걸쳐 2를 찾았는데, 앞에서 찾았으므로 좌측으로 순환을 1회 시켜준 후 pop을 진행합니다.

 

덱 : {3, 4, 5, 1}

 

이후 찾는 숫자를 모두 pop할 때까지 반복합니다.

코드

---

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

int main()
{
    int N, M;
    cin >> N >> M;
    deque<int> dq;
    for(int i = 0; i < N; i++) dq.push_back(i + 1);
    int result = 0;
    for(int i = 0; i < M; i++)
    {
        int count = 0;
        int input;
        deque<int>::iterator itb = dq.begin();
        deque<int>::iterator ite = dq.end();
        *dq.end() = 0;		//pop하고 나서 덱의 end를 0으로 초기화
        cin >> input;
        while(count <= N / 2)
        {
            if(*itb == input)	//덱의 앞쪽에서 발견되었을 경우
            {
                for(int j = 0; j < count; j++)
                {
                    dq.push_back(dq.front());
                    dq.pop_front();
                }
                break;
            }
            else if(*ite == input)	//덱의 뒤쪽에서 발견되었을 경우
            {
                for(int j = 0; j < count; j++)
                {
                    dq.push_front(dq.back());
                    dq.pop_back();
                }
                break;
            }
            itb++;
            ite--;
            count++;
        }
        N--;
        dq.pop_front();
        result += count;
    }
    
    cout << result << "\n";
    return 0;
}

 

그 외

---