굳건하게

문제 : https://www.acmicpc.net/problem/5430

[알고리즘풀이]

R을 만나면 방향을 바꿔서 삽입, 삭제를 진행해야되므로 양방향에서 삽입, 삭제를 할 수 있는 deque(덱)을 이용한다.

deque(덱) 자료구조 설명 : https://www.acmicpc.net/problem/5430

#include<iostream>
#include<string>
#include<deque>

using namespace std;

int main(void){
	int t;
	cin >> t;
	while (t--) {
		deque<int> dq;
		int n, dir = 1;
		bool flag = false;
		string in1, in2;
		cin >> in1 >> n >> in2;
		int i = 1;
		while (i < in2.length()) {
			string temp = "\n";
			while (1) {
				if (in2[i] == ',' || in2[i] == ']')
					break;
				else{
					temp += in2[i];
					i++;
				}
			}
			if (temp == "\n") {
				break;
			}
			else{
				dq.push_back(stoi(temp));
				i++;
			}
		}

		for (int i = 0; i < in1.length(); i++) {
			if (in1[i] == 'D') {
				if (dq.empty()) {
					cout << "error\n";
					flag = true;
					break;
				}
				else if (dir) 
					dq.pop_front();
				else
					dq.pop_back();
			}
			if (in1[i] == 'R') {
				if (dir)
					dir = 0;
				else
					dir = 1;
			}
		}
		if (flag)
			continue;
		if (dir) {
			cout << '[';
			while (!dq.empty()) {
				if (dq.size() == 1)
					cout << dq.front();
				else{
					cout << dq.front() << ',';
				}
				dq.pop_front();

			}
			cout << "]\n";
		}
		else {
			cout << '[';
			while (!dq.empty()) {
				if (dq.size() == 1)
					cout << dq.back();
				else {
					cout << dq.back() << ',';
				}
				dq.pop_back();
			}
			cout << "]\n";
		}
	}

}

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

[알고리즘풀이]

왼쪽, 오른쪽으로 회전하는 것을 덱을 이용해 양쪽에서 삽입, 삭제를 진행하면 된다.

덱에 1 ~ n 까지 삽입하고, 원하는 값이 몇 번째에 있는지 구한다.

그러면, 현재 front에서 왼쪽 / 오른쪽 중 어디로 순회하는 것이 적게 이동하는지 판단할 수 있고,

이동하며 횟수를 계속 Count 해주면 된다.

#include<iostream>
#include<deque>
#include<algorithm>

using namespace std;

int m_l[50];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	deque<int> dq;
	int n, m, answer = 0;

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		dq.push_back(i);
	for (int i = 0; i < m; i++)
		cin >> m_l[i];

	for (int i = 0; i < m; i++) {
		if (dq.front() == m_l[i]){
			dq.pop_front();
			continue;
		}
		int inx = 0;
		for (int j = 0; j < dq.size(); j++)
			if (dq[j] == m_l[i])
				break;
			else
				inx = j;
		int r = 0, l = 0;
		// 오른쪽으로간다.
		if (inx < (dq.size() / 2)) {
			while (dq.front() != m_l[i]) {
				int temp = dq.front();
				dq.pop_front();
				dq.push_back(temp);
				r++;
			}
			dq.pop_front();
			answer += r;
		}
		// 왼쪽으로간다.
		else {
			while (dq.front() != m_l[i]) {
				int temp = dq.back();
				dq.pop_back();
				dq.push_front(temp);
				l++;
			}
			dq.pop_front();
			answer += l;
		}
	}
	cout << answer;
}

문제 : https://www.acmicpc.net/problem/10866

[알고리즘풀이]

Deque(덱) 자료구조를 이용한 문제로 입력된 명령을 그대로 수행하면 된다.

Deque(덱) 자료구조 설명 : https://travelbeeee.tistory.com/60?category=807507

#include<iostream>
#include<string>
#include<deque>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
	deque<int> dq;
	string input;
	int n;
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input;
		if (input == "push_front") {
			int temp;
			cin >> temp;
			dq.push_front(temp);
		}
		else if (input == "push_back") {
			int temp;
			cin >> temp;
			dq.push_back(temp);
		}
		else if (input == "pop_front") {
			if (dq.empty())
				cout << "-1\n";
			else {
				cout << dq.front() << '\n';
				dq.pop_front();
			}
		}
		else if (input == "pop_back") {
			if (dq.empty())
				cout << "-1\n";
			else {
				cout << dq.back() << '\n';
				dq.pop_back();
			}
		}
		else if (input == "size") {
			cout << dq.size() << '\n';
		}
		else if (input == "empty") {
			if (dq.empty())
				cout << "1\n";
			else
				cout << "0\n";
		}
		else if (input == "front") {
			if (dq.empty())
				cout << "-1\n";
			else
				cout << dq.front() << '\n';
		}
		else {
			if (dq.empty())
				cout << "-1\n";
			else
				cout << dq.back() << '\n';
		}
	}
}

문제 : https://www.acmicpc.net/problem/1966

[알고리즘풀이]

이름부터 Queue를 이용하는 문제다.

Queue에 있는 중요도 중 가장 큰 값을 찾고,

Queue의 가장 앞에 있는 문서의 중요도가 가장 큰 값과 같다면 Pop을 하고, 아니면 뒤로 Push한다.

이때, Queue의 가장 앞에 있는 문서의 중요도가 가장 크면서, 내가 찾는 문서라면 알고리즘을 종료하며

지금까지 Pop이 일어난 횟수(나보다 앞에서 나간 문서의 수)를 출력해주면 된다.

#include<iostream>
#include<queue>

using namespace std;

int main(void) {
	int t;
	cin >> t;
	while (t--) {
		queue<int> q;
		int n, m;
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			q.push(x);
		}
		bool flag = true;
		int count = 1, max;
		while (1) {
			if(flag){
				max = 0;
				for (int i = 0; i < q.size(); i++) {
					if (max < q.front())
						max = q.front();
					q.push(q.front());
					q.pop();
				}
			}
			if (m == 0 && q.front() == max) {
				cout << count << '\n';
				break;
			}
			else if (m == 0 && q.front() != max) {
				m = q.size() - 1;
				q.push(q.front());
				q.pop();
				flag = false;
			}
			else if (q.front() == max) {
				count++;
				q.pop();
				m--;
				flag = true;
			}
			else {
				q.push(q.front());
				q.pop();
				m--;
				flag = false;
			}
		}
	}

}

[주의할점]

queue에서 max 값을 찾기 위해서는 queue를 순회하며 pop, push를 진행해야 된다.

즉, max 값을 찾는 행위 자체가 시간을 많이 잡아먹는다.

따라서, max가 변하지 않는 경우에는 max 값을 찾는 행위를 하지 않으며 시간을 줄여야 된다.