알고리즘 :: 백준 :: 구현 :: 3425 :: 고스택

Embedded June·2021년 8월 3일
0

알고리즘::백준

목록 보기
102/109

1. 문제 분석하기

1.1. 문제 의도

  • 이번 문제의 유형은 시뮬레이션구현입니다.
  • 문제를 읽고 복잡한 조건을 잘 정리한 뒤 빠짐없이 구현하는 능력이 필요합니다.

1.2. 문제 조건

  1. stack 자료구조를 사용한다.
  2. 이항연산은 pop()을 2회 수행하고 계산결과를 push()한다.
  3. 나눗셈의 경우 다음과 같이 계산한다.
    1. 피연산자는 모두 절대값으로 취급하고 계산한다.
    2. 피연산자의 음수 개수가 하나일 때 몫을 음수로 바꾼다.
    3. 피연산자의 음수 개수가 0개 또는 2개일 때는 그냥 둔다.
  4. 프로그램 에러는 다음과 같은 경우다. 에러가 발생하면 수행을 멈춘다.
    1. 연산에 필요한 숫자가 부족한 경우
    2. 0으로 나누는 경우
    3. 연산 결과의 절댓값이 1e9를 넘어가는 경우
    4. 모든 수행이 종료됐을 때 스택에 2개 이상의 수가 저장되는 경우

2. 문제 해결하기

image-20210804005034654.

  • 이 문제는 문제 자체는 이해하기 쉽지만, 예제를 이해하기 힘듭니다.
  • 컴퓨터 A, B, C를 구분해서 입력받아야 합니다.
    string operation;
    while(cin >> operation) {
        if (operation == "QUIT") return 0;
        if (operation == "END") break;
        int operand = 0;
        if (operation == "NUM") cin >> operand;
        commands.push_back({changeFormat(operation), operand});
    }
  • while(cin >> operation)을 사용하면 빈 줄을 입력받을 때 while문을 탈출합니다.
  • QUIT 명령어와 END 명령어를 입력받으면 while문을 탈출합니다.
  • NUM 명령어인 경우 뒤에 숫자가 오므로 추가로 operand를 입력받습니다. 그 외에는 0입니다.
  • changeFormet() 함수는 switch-case 문을 사용하기 위해 operation을 해당하는 번호로 매핑합니다.
  • 명령어 뒤에 오는 일련의 숫자는 테스트케이스에 들어갈 숫자입니다. 가장 처음에 stack 안에 있는 숫자입니다.
  • 연산 결과가 int 범위를 넘어갈 수 있으므로 long long을 사용합니다.
  • 모든 명령어는 구현이 간단하지만, 나눗셈 연산이 조금 까다롭습니다.
    • 피연산자들 중 음수의 개수를 파악하기 위한 간단한 방법은 아래와 같습니다.
    int cnt = (왼쪽 < 0) + (오른쪽 < 0);
    stk.push((abs(오른쪽) / abs(왼쪽)) * (cnt % 2 ? -1 : 1));
  • cnt가 홀수인지 짝수인지에 따라 몫에 1 또는 -1을 곱해줍니다.
  • 에러를 발견한다면 즉시 실행을 종료합니다.

3. 코드

#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;
using ll = long long;

vector<pair<int, int>> commands;

int changeFormat(const string& s) {
	if (s == "NUM") return 0;
	if (s == "POP") return 1;
	if (s == "INV") return 2;
	if (s == "DUP") return 3;
	if (s == "SWP") return 4;
	if (s == "ADD") return 5;
	if (s == "SUB") return 6;
	if (s == "MUL") return 7;
	if (s == "DIV") return 8;
	if (s == "MOD") return 9;
	return -1;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
	while(1) {
		commands.clear();
		
		// 하나의 기계에 대한 명령어를 입력받는다.
		string operation;
		while(cin >> operation) {
			if (operation == "QUIT") return 0;
			if (operation == "END") break;
			int operand = 0;
			if (operation == "NUM") cin >> operand;
			commands.push_back({changeFormat(operation), operand});
		}
		
		int testCase = 0;
		cin >> testCase;
		while(testCase--) {
			int inputVar = 0;
			cin >> inputVar;
			
			stack<ll> stk;
			stk.push(inputVar);
			
			bool errFlag = false;
			for (const auto& cmd : commands) {
				if (errFlag) break;
				
				switch(cmd.first) {
				case 0:	// NUM X operation
					stk.push(cmd.second);
					break;
				case 1: // POP operation
					if (stk.empty()) errFlag = true;
					else stk.pop();
					break;
				case 2: // INV operation
					if (stk.empty()) errFlag = true;
					else {
						ll lhs = stk.top(); stk.pop();
						stk.push(-lhs);
					}
					break;
				case 3:	// DUP operation
					if (stk.empty()) errFlag = true;
					else stk.push(stk.top());
					break;
				case 4:	// SWP operation
					if (stk.size() < 2) errFlag = true;
					else {
						ll lhs = stk.top(); stk.pop();
						ll rhs = stk.top(); stk.pop();
						stk.push(lhs);
						stk.push(rhs);
					}
					break;
				case 5:	// ADD operation
					if (stk.size() < 2) errFlag = true;
					else {
						ll lhs = stk.top(); stk.pop();
						ll rhs = stk.top(); stk.pop();
						ll sum = lhs + rhs;
						if (abs(sum) > 1e9) errFlag = true;
						else stk.push(sum);
					}
					break;
				case 6:	// SUB operation
					if (stk.size() < 2) errFlag = true;
					else {
						ll lhs = stk.top(); stk.pop();
						ll rhs = stk.top(); stk.pop();
						ll sum = rhs - lhs;
						if (abs(sum) > 1e9) errFlag = true;
						else stk.push(sum);
					}
					break;
				case 7:	// MUL operation
					if (stk.size() < 2) errFlag = true;
					else {
						ll lhs = stk.top(); stk.pop();
						ll rhs = stk.top(); stk.pop();
						ll sum = lhs * rhs;
						if (abs(sum) > 1e9) errFlag = true;
						else stk.push(sum);
					}
					break;
				case 8:	// DIV operation
					if (stk.size() < 2) errFlag = true;
					else {
						ll lhs = stk.top(); stk.pop();
						ll rhs = stk.top(); stk.pop();
						if (lhs == 0) errFlag = true;
						else {
							// 피연산자들 중 음수의 개수를 체크한다.
							int negativeCnt = (lhs < 0) + (rhs < 0);
							stk.push((abs(rhs) / abs(lhs)) * (negativeCnt % 2 ? -1 : 1));
						}
						break;
					}
				case 9:	// MOD operation
					if (stk.size() < 2) errFlag = true;
					else {
						ll lhs = stk.top(); stk.pop();
						ll rhs = stk.top(); stk.pop();
						if (lhs == 0) errFlag = true;
						else stk.push(rhs % lhs);
					}
					break;
				}
			}
			if (errFlag == true || stk.size() != 1) cout << "ERROR\n";
			else cout << stk.top() << '\n'; 
		}
		cout << '\n';
	}
}

4. 결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글