BOJ/백준 19591 독특한 계산기

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

 

해결 아이디어

문자열 처리 부분만 잘 해주고 조건에 맞게 잘 비교하면 되는 문제였다

 

#include <iostream>
#include <deque>
#include <string>
#include <cstdlib>
using namespace std;

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

    string str;
    cin >> str;

    deque<long long> num;
    deque<char> op;
    string number = "";


    bool sign = false; // 부호 판별 변수 시작할때 음수 판별
    int len = str.length();
    
    for(int i = 0; i < len; i++){
        if(i == 0 && str[i] == '-') sign = true;
        else if(!isdigit(str[i])){ // 숫자가 아니면 
            op.push_back(str[i]); // 연산자를 디큐에 넣고
            long long tmp = stoll(number); // 임시 숫자 변수를 long long 타입으로 변환
            if(sign){ // 음수 일때
                tmp *= -1;
                sign = false;
            }
            num.push_back(tmp); // 숫자 deque에 push
            number = ""; // 초기화
        }
        else{
            number += str[i]; // 숫자 이면 계속 문자열에 이어 붙여 줌
			      // 1+2*90 이럴 경우 1, 2, 90 으로 넣어야 하기 때문
        }
        // 만약 모든 요소에 대한 검사가 끝나면 마지막 요소를 추가
        if(i == len - 1){
            long long tmp = stoll(number);
            if(sign){
                tmp *= -1;
                sign = false;
            }
            num.push_back(tmp);
            number = "";
        }
    }
		
    // 계산하는 함수 현재 인덱스와 + 1 인덱스를 계산
    auto calc = [](deque<long long>& num, int idx, char op) -> long long {
        if(op == '*') return num[idx] * num[idx + 1];
        else if(op == '/') return num[idx] / num[idx + 1];
        else if(op == '+') return num[idx] + num[idx + 1];
        else return num[idx] - num[idx + 1];
    };
		
    // 비교 함수
    auto cmp = [](char op) -> int {
        if(op == '*' || op == '/') return 2;
        else return 1;
    };
		
    // 숫자가 1개가 남을 때 까지 
    while(num.size() > 1 && !op.empty()){
        char op_front = op.front(), op_rear = op.back();
        long long cur_front = 0, cur_rear = num.size() - 2;
        long long calc_front = calc(num, cur_front, op_front), calc_rear = calc(num, cur_rear, op_rear);
        bool front = false, rear = false;
				
	// 우선순위 비교 곱셈, 나눗셈인지 앞 계산 결과가 큰지 뒤가 큰지
        if(cmp(op_front) > cmp(op_rear)) front = true;
        else if(cmp(op_front) < cmp(op_rear)) rear = true;
        else if(calc_front >= calc_rear) front = true;
        else rear = true;
				
	// 앞의 계산부터 진행할 경우
        if(front){
            num.pop_front();
            num.pop_front();
            num.push_front(calc_front);

            op.pop_front();
        }
        // 뒤의 계산부터 진행 할 경우
        else{
            num.pop_back();
            num.pop_back();
            num.push_back(calc_rear);

            op.pop_back();
        }
    }
		
    // 정답 출력
    cout << num.front();
    return 0;
}

 

문제는 풀면서 어처구니 없는 실수를 너무 많이 했다.

long long을 써야하는데 int를 사용해서 틀리거나, 

    // 계산하는 함수 현재 인덱스와 + 1 인덱스를 계산
    auto calc = [](deque<long long>& num, int idx, char op) -> long long {
        if(op == '*') return num[idx] * num[idx + 1];
        else if(op == '/') return num[idx] / num[idx + 1];
        else if(op == '+') return num[idx] + num[idx + 1];
        else return num[idx] - num[idx + 1];
    };

여기서 &을 사용하지 않고 참조가 아닌 복사로 보내주면 시간초과가 발생한다 숫자의 범위가 커서 매우 많은 데이터를 복사한다고

그런 일이 발생 한 것 같았다.