백준1021 - 회전하는 큐

 

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

1021번: 회전하는 큐

문제에서 회전한다는 힌트를 주어서 deque를 이용하였다.

지우려는 위치에서 처음 값에서의 차와 마지막 값에서의 차를 이용하여 처음 값과 가까우면 2번을 수행하고 마지막 값과 가까우면 3번을 수행하게 하였다.

 

ex)

5 5

4 2 3 1 5

 

1. 4 삭제 -> 2번

5 1 2 3 4

4 5 1 2 3

5 1 2 3

 

2. 2 삭제 -> 2번

3 5 1 2

2 3 5 1

3 5 1

 

3. 3 삭제 -> 0번

5 1

 

4. 1 삭제 -> 1번

1 5

5

 

5. 5 삭제 -> 0번

 

총 수행 횟수 : 2 + 2 + 0 + 1 + 0 = 5

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

int main() {
	deque<int> deq;
	vector<int> v;
	int n, m;
	int sum = 0;

	cin >> n >> m;
	
	//deq의 n번째 원소는 n이라고 가정하고 deq를 초기화
	for (int i = 1; i <= n; i++) {
		deq.push_back(i); 
	}

	//원하는 순서의 수 입력
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		v.push_back(a); 
	}
    
        //원하는 위치에 수를 지우는 과정
	for (int i = 0; i < v.size(); i++) {
		int want_pop = v[i]; //원하는 수 입력
		int cnt = 0 //반복횟수
		for (int j = 0; j < deq.size(); j++) {
			if (deq[j] == want_pop) {
				if (abs(j - 0) < abs(j - int(deq.size()))) { //front와 가까운 곳, 2를 수행
					while (1) {
						//뽑으려는 수가 deq의 맨 앞으로 나오면 탈출
						if (deq.front() == want_pop) {
							break;
						}

						cnt++; //반복 횟수 증가

						//맨 앞자리와 맨 뒷자리를 바꿔준다.
						int tmp = deq.front();
						deq.pop_front();
						deq.push_back(tmp);
					}
				}
				else { //rear와 가까운 곳, 3을 수행
					while (1) {
						//뽑으려는 수가 deq의 맨 앞으로 나오면 탈출
						if (deq.front() == want_pop) {
							break;
						}

						cnt++; //반복 횟수 증가

						//맨 뒷자리와 맨 앞자리를 바꿔준다.
						int tmp = deq.back();
						deq.pop_back();
						deq.push_front(tmp);
					}
				}
				deq.pop_front(); //맨 앞자리를 팝
				break;
			}
		}
		sum = sum + cnt; //반복 횟수를 더한다.
	}
	cout << sum;
}