[BOJ/C++] 백준 28078 - 중력 큐

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

28078번: 중력 큐

자료구조 중 큐의 앞, 뒤에 원소를 추가하고 꺼낼 수 있는 자료구조인 deque를 사용하는 것이 핵심인 문제이다.

front(), push(), pop()만을 사용하던 기존 queue 자료구조와 다르게 push_front(), push_back(), pop_front(), pop_back(), front(), back()의 함수를 사용할 수 있다. 

 

각각의 쿼리에 대해서 행위를 하였을 때, 공과 가림막의 개수, 그리고 큐의 상태를 변수로 표현하여 해결하였다. 

#include <iostream>
#include <deque>
#include <vector>
#define endl '\n'
using namespace std;

deque<char> q;
bool flag = 1; // 가로 방향이면 1, 세로 방향이면 0
int ball = 0;
int wall = 0;
int isLeft = 1;  // 가로 방향일 때, 뒤 쪽 방향이 왼쪽에 있다면 1, 오른쪽에 있다면 0
int isUpper = 1; // 세로 방향일 때, 뒤 쪽 방향이 위에 있다면 1, 아래에 있다면 0

void query(string s, char c) {
	if (s == "push") {
		if (flag == 1) { // 가로
			q.push_back(c);
			if (c == 'w') wall++;
			else ball++;
		}
		else {  // 세로
			if (c == 'w') {
				q.push_back(c);
				wall++;
			}
			else {
				if (isUpper) { // 뒤가 위에 있는 경우
					if (!q.empty()) {
						char nc = q.front();
						if (nc == 'w') {
							q.push_back(c);
							ball++;
						}
					}
				}
			}
		}
	}
	else if (s == "count") {
		if (c == 'b') {
			cout << ball << endl;
		}
		else
			cout << wall << endl;
	}
	else if (s == "pop") {
		if (!q.empty()) {
			if (flag) {
				char nc = q.front();
				if (nc == 'b') ball--;
				else wall--;
				q.pop_front();
			}
			else { // 세로 방향인 경우
				if (isUpper) {  // 아래에서 꺼내는 경우
					wall--; 
					q.pop_front();
					while (!q.empty()) {
						char nc = q.front(); 
						if (nc == 'w') break;
						q.pop_front(); 
						ball--; 
					} // 가림막 위에 있던 공이 쏟아진다.
				}
				else { // 위에서 꺼내는 경우
					char nc = q.front(); 
					if (nc == 'b') ball--;
					else wall--; 
					q.pop_front(); 
				}
			}
		}
	}
	else if (s == "rotate") {
		flag = 1 - flag;
		if (!flag) { // 세로 방향이 되었다면
			if (c == 'l') { // 반시계 방향 회전
				// 위가 앞, 아래가 뒤가 된 경우
				if (isLeft == 1) {
					if (!q.empty()) {
						char nc = q.back();
						while (!q.empty()) {
							nc = q.back();
							if (nc == 'w') break;
							q.pop_back();
							ball--;
						}
					}
					isUpper = 0;
				}
				else { //  위가 뒤, 아래가 앞이 된 경우
					// 앞에 있는 공들이 쏟아져나온다. 
					if (!q.empty()) {
						char nc = q.front();
						while (!q.empty()) {
							nc = q.front();
							if (nc == 'w') break;
							q.pop_front();
							ball--;
						}
					}
					isUpper = 1;
				}
			}
			else if (c == 'r') { // 시계 방향 회전 
				if (isLeft == 1) {
					if (!q.empty()) {
						char nc = q.front();
						while (!q.empty()) {
							nc = q.front();
							if (nc == 'w') break;
							q.pop_front();
							ball--;
						}
					}
					isUpper = 1;
				}
				else {
					if (!q.empty()) {
						char nc = q.back();
						while (!q.empty()) {
							nc = q.back();
							if (nc == 'w') break;
							q.pop_back();
							ball--;
						}
					}
					isUpper = 0;
				}

			}
		}
		else {  // 가로 방향이 되었다면
			if (c == 'l') { // 반시계 방향 회전
				if (isUpper == 1)
					isLeft = 1;
				else
					isLeft = 0;
			}
			else {
				if (isUpper == 1)
					isLeft = 0;
				else
					isLeft = 1;
			}
		}
	}
}

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

	int q; cin >> q;
	for (int i = 0; i < q; i++) {
		string s; cin >> s;
		char c;
		if (s != "pop") {
			cin >> c;
		}
		query(s, c);
	}
	return 0;
}

신경 써야 하는 부분은 아래와 같다. 

 

1) rotate 시 현재 큐의 앞, 뒤의 방향 혹은 세로, 가로 방향임을 고려하여 isLeft, isUpper 변수를 적절히 변경해준다. 그리고 내부의 공이 쏟아져야 하는 경우에는 모든 공을 쏟게 한다.

 

2) 세로 방향의 큐에 push하는 경우 가림막의 여부를 고려하여 push한다. 만약 큐의 뒤가 아래 쪽에 있는 경우에 push한다면 그게 공이든, 가림막이든 push할 수 없다.

 

3) ⭐ 세로 방향의 큐의 앞쪽에서 pop하는 경우, 앞쪽이 아래에 있는 방향이라면 pop하게 되는 원소가 있다면 그것은 가림막일 것이다. (공은 이전에 rotate 연산에서 모두 쏟아졌다.) 따라서 가림막을 제거하였을 때 그 위에 있는 공들이 쏟아지는 경우를 고려해야 한다.