[BOJ] 28078번_중력 큐_덱 (C++)

[문제]

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

왼쪽이 뒤, 오른쪽이 앞인 가로 방향의 빈 큐가 존재한다. 이 때 공이나 가림막을 큐의 뒤에 삽입하거나, 큐의 앞에서 공이나 가림막을 꺼낼 수 있으며, 큐를 시계방향이나 반시계 방향으로 90도 회전시킬 수 있다.

큐 안의 공은 중력의 영향을 받고 가림막은 중력의 영향을 받지 않는다. 따라서 큐가 세로 방향으로 세워졌을 때 큐의 가장 아래에 있는 가림막보다 아래에 있는 공들은 모두 밖으로 떨어지게 된다.

Q개의 쿼리가 주어질때, 쿼리들을 순서대로 수행하는 프로그램을 작성하는 문제이다.

쿼리는 다음과 같다.

• push b : 큐의 뒤에 공 하나를 삽입한다.
• push w : 큐의 뒤에 가림막 하나를 삽입한다.
• pop : 큐에서 가장 앞쪽에 있는 공이나 가림막을 하나 꺼낸다. 큐가 빈 상태면 아무 일도 일어나지 않는다.
• rotate l : 큐를 반시계 방향으로 90도 회전시킨다.
• rotate r : 큐를 시계 방향으로 90도 회전시킨다.
• count b : 현재 큐에 들어있는 공의 개수를 출력한다.
• count w : 현재 큐에 들어있는 가림막의 개수를 출력한다.

[사용 알고리즘]

덱

[풀이 핵심]

• 큐를 사용해야 될 것 같은 문제지만, 방향에 따라 pop하는 위치가 다르므로 덱을 사용하는 것이 편하다.
• 문제에 주어진 쿼리를 하나씩 구현하는 것이 핵심

  • push b : 가로 방향(rotate == 0 || rotate == 2)일 땐 공을 push하고, 앞이 위를 바라보는 세로 방향(rotate == 1)이면서, 가림막이 존재할 경우에도 공을 push한다. 그리고 앞이 아래를 바라보는 세로 방향(rotate == 3)일 경우엔 공을 넣자마자 빠지므로 continue를 해준다. 그리고 push하는 경우에는 공의 개수를 늘려준다.
  • push w : 가림막은 중력의 영향을 받지 않으므로 방향에 상관없이 가림막을 push해주고 가림막의 개수를 늘려준다.
  • pop : 방향이 1인 경우 빼곤 덱의 뒤에서 pop해준 후 공인지 가림막인지만 판별해서 개수를 감소시켜준다. 방향이 1인 경우에는 가림막을 뺐을 때, 공이 중력에 의해 밖으로 떨어 질수 있으므로 가림막을 pop해준 후 다음 원소가 공일 경우 전부 pop해주고 공의 개수를 감소시키는 처리를 해준다.
  • rotate l : 큐를 반시계 방향으로 돌린 후 세로 방향일 때(rotate == 1 || rotate == 3) 중력에 의해 떨어지는 공을 pop해주고 공의 개수를 감소시키는 처리를 한다. (방향에 맞게 pop_back() 또는 pop_front()를 해준다.)
  • rotate r : 큐를 시계 방향으로 돌린 후 rotate l과 동일하게 중력에 의한 처리를 해준다.
  • count b : 위에서 계산한 현재 큐에 들어있는 공의 개수를 출력한다.
  • count w : 위에서 계산한 현재 큐에 들어있는 가림막의 개수를 출력한다.

[코드]

//boj28078번_중력 큐_자료구조(덱)

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int Q;
	cin >> Q;

	cin.ignore();

	deque<char> d;

	int rotate = 0;

	int b_count = 0;
	int w_count = 0;

	for (int i = 0; i < Q; i++) {
		string cmd;
		getline(cin, cmd);

		if (cmd == "push b") {
			if (rotate == 0 || rotate == 2) {
				d.push_front('b');
				b_count++;
			}
			else if (rotate == 1) {
				if (!d.empty() && d.back() == 'w') {
					d.push_front('b');
					b_count++;
				}
			}
			else if (rotate == 3) {
				continue;
			}
		}
		else if (cmd == "push w") {
			d.push_front('w');
			w_count++;
		}
		else if (cmd == "pop") {
			if (!d.empty()) {
				if (rotate == 1) {
					if (d.back() == 'w') {
						d.pop_back();
						w_count--;

						while (!d.empty()) {
							if (d.back() == 'b') {
								d.pop_back();
								b_count--;
							}
							else {
								break;
							}
						}
					}
				}
				else {
					if (d.back() == 'b') {
						d.pop_back();
						b_count--;
					}
					else if (d.back() == 'w') {
						d.pop_back();
						w_count--;
					}
				}
			}
		}
		else if (cmd == "rotate l") {
			rotate = (rotate + 3) % 4;

			if (rotate == 1) {
				while (!d.empty()) {
					if (d.back() == 'b') {
						d.pop_back();
						b_count--;
					}
					else {
						break;
					}
				}
			}
			else if (rotate == 3) {
				while (!d.empty()) {
					if (d.front() == 'b') {
						d.pop_front();
						b_count--;
					}
					else {
						break;
					}
				}
			}
		}
		else if (cmd == "rotate r") {
			rotate = (rotate + 1) % 4;

			if (rotate == 1) {
				while (!d.empty()) {
					if (d.back() == 'b') {
						d.pop_back();
						b_count--;
					}
					else {
						break;
					}
				}
			}
			else if (rotate == 3) {
				while (!d.empty()) {
					if (d.front() == 'b') {
						d.pop_front();
						b_count--;
					}
					else {
						break;
					}
				}
			}
		}
		else if (cmd == "count b") {
			cout << b_count << '\n';
		}
		else if (cmd == "count w") {
			cout << w_count << '\n';
		}
	}

	return 0;
}