[BOJ/Silver 1] 백준 21737 SMUPC 계산기(C++)

문제 링크

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

21737번: SMUPC 계산기

 

 

문제

SMUPC를 기념하기 위해 ALGOS와 DSC Sookmyung에서는 SMUPC의 각 글자로 계산이 이루어지는 계산기를 만들었다. 가은이와 혜민이는 이 계산기와 같은 방식으로 작동하는 프로그램을 만들고자 한다. 가은이와 혜민이는 몇 가지 계산 작업을 통해 SMUPC에 해당하는 각 기호가 아래의 표와 같이 동작함을 밝혀낼 수 있었다.

[SMUPC 계산기의 동작 방식]

알파벳	S	M	U	P	C
해당 수식	-	*	/    (정수 몫    나눗셈)	+	여태까지의 계산 결괏값 반환

SMUPC 계산기는 기존의 사칙연산 방식과는 다르게 앞에서부터 순서대로 계산이 이루어진다. 단, 이 계산기에서 음수를 양수로 나누는 경우는 C++14의 기준을 따른다. 이는 음수에 -1을 곱해 양수로 바꾼 뒤 몫을 취하고, 그 몫에 -1을 곱한 것과 같다. 예를 들어, 5/3=1, (-5) /3=-1로 계산된다. 더불어 SMUPC 계산기에 입력하는 수식은 다음과 같은 규칙을 따라야 한다고 한다.

• 수식은 0부터 9까지의 숫자와 S, M, U, P, C의 알파벳만을 포함할 수 있다.
• 수식은 수로 시작해야 하며, 알파벳으로 끝나야 한다.
• 수식에 음수를 입력할 수 없다.
• 수식에 입력하는 수는 0으로 시작할 수 있다.
• 알파벳 C로 계산 결괏값을 반환한 후에 추가적인 계산을 원한다면 알파벳 기호를 추가적으로 사용하여 입력을 이어나가야 한다.
• 알파벳 S, M, U, P는 서로 연속해서 입력할 수 없으며 알파벳 S, M, U, P을 입력한 직후 다른 수의 입력 없이 알파벳 C를 바로 입력할 수 없다.

SMUPC 계산기와 같은 작업을 수행할 수 있는 프로그램을 작성하여라.

입력

첫째 줄에 수식에 들어갈 기호의 개수 N(1≤N≤500000)이 주어진다.

둘째 줄에 N개의 기호가 사용된 수식이 주어진다. 수식의 길이는 1000000을 넘지 않는다. 단, 계산 도중 입력되는 수나 계산 결괏값의 범위는 -2^31이상 2^31-1이하이다. 더불어 어떤 수를 0으로 나누는 경우는 존재하지 않는다.

출력

알파벳 C가 나올 때마다 여태까지의 계산 결과 값을 띄어쓰기 간격으로 출력하도록 한다. 알파벳 C가 한번도 나오지 않을 경우 NO OUTPUT을 출력한다.

예제 입력 1

5
3S2M3U1P2C

예제 출력 1

5

예제 입력 2

4
0328CS00325CC

예제 출력 2

328 3 3

예제 입력 3

1
000232738S

예제 출력 3

NO OUTPUT

알고리즘 분류

• 문자열
• 자료 구조

풀이

우선 숫자와 S, M, U, P, C를 queue에 push하였다. push하는 과정에서 C의 개수를 세었다.

그리고 queue에서 숫자와 S, M, U, P, C를 꺼내면서, S, M, U, P가 나왔을 때에는 다음 수를 같이 꺼내서 계산하고, C가 나왔을 때에는 현재 숫자를 Answer 벡터에 담았다. 더 이상 꺼낼 C가 없다면 이 이후로는 계산해도 무의미하므로 break해주었다.

Answer 벡터가 비어있다면 NO OUTPUT을 출력하고, 비어있지 않다면 0번째 원소부터 차례대로 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 50001
#define LL long long
#define INF 1e9

using namespace std;
int N;
string Sentence;
queue<string> Q;
int Cur;
int Flag = 0;
vector<int> Answer;

int Calc(int A, int B, string OP) {
	if (OP == "S") {
		return (A - B);
	}
	else if (OP == "M") {
		return (A * B);
	}
	else if (OP == "U") {
		if (A >= 0) {
			return (A / B);
		}
		else {
			int res = (-A) / B;
			return -res;
		}
	}
	else if (OP == "P") {
		return (A + B);
	}
}

void Input() {
	cin >> N;
	cin >> Sentence;
}

void Settings() {
	string Number = "";
	for (int i = 0; i < Sentence.size(); i++) {
		char C = Sentence[i];
		if ((C >= '0') && (C <= '9')) {
			Number += C;
		}
		else {
			if (Number != "") {
				Q.push(Number);
				Number = "";
			}
			if (C == 'C') {
				Flag++;
			}
			Number += C;
			Q.push(Number);
			Number = "";
		}
	}
	if (Flag > 0) {
		while (!Q.empty()) {
			string QF = Q.front();
			Q.pop();
			if ((QF == "S") || (QF == "M") || (QF == "U") || (QF == "P")) {
				string QF2 = Q.front();
				Q.pop();
				int Next = stoi(QF2);
				Cur = Calc(Cur, Next, QF);
			}
			else if (QF == "C") {
				Answer.push_back(Cur);
				Flag--;
				if (Flag == 0) {
					break;
				}
			}
			else {
				Cur = stoi(QF);
			}
		};
	}
}

void Find_Answer() {
	if (Answer.size() > 0) {
		for (int i = 0; i < Answer.size(); i++) {
			cout << Answer[i] << " ";
		}
		cout << "\n";
	}
	else {
		cout << "NO OUTPUT\n";
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}