백준 19591번 독특한 계산기

🔒[문제 url]

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

🔑알고리즘

1. 문자열을 파싱해 수와 연산자를 분리한다.
   수는 vector에 push하고
   연산할 수의 위치를 나타내는 변수left , right도 선언한다.
   연산자는 맨 앞 혹은 맨 뒤의 것이 수행되므로, deque에 push한다.
2. 문제의 조건에 따라 연산을 진행한다.
   앞의 연산자가 수행될 경우 vector[left]와 vector[left+1]를 연산하고, 뒤의 연산자가 수행될 경우 vector[right-1]와 vector[right] 연산한다.
   연산 결과는 각각 vector[left+1]과 vector[right-1]에 담긴다.

• 문자열은 어떻게 파싱하는가?
  1. 문자열을 순회하며 첫 번째 연산자를 제외하고, 연산자가 나올 때까지 문자열 token에 붙인다.
     • 첫 번째 수가 음수일 수 있으므로 첫 번째 연산자는 제외한다.
  2. 연산자를 만났다면, token은 수이므로 vector에 넣고, 연산자는 deque에 push한다.
  3. 문자열 끝까지 1 2를 반복한다.
  4. 아직 vector에 삽입되지 않은 마지막 수, 즉 token을 삽입한다.

🐾부분 코드

bool oper1(char c)
{//mult or div
    return c=='*'||c=='/';
}

bool oper2(char c)
{//plus or minus
    return c=='+'||c=='-';
}

<연산자 구별 함수>
우선순위를 구별하기 위해 두 개의 함수로 나눈다.

void Parsing()
{//수와 연산자 분리

    string token = "";
    for(int i = 0; i < str.length(); i++)
    {
        //연산자라면
        if(i && (oper1(str[i]) || oper2(str[i])))
            num.push_back(stoll(token)),
                    token = "",
                    oper.push_back(str[i]);
            //수라면
        else token += str[i];
    }num.push_back(stoll(token));
}

<문자열 파싱 함수>
위에서 설명한 알고리즘에 따라 수와 연산자를 분리한다.
이때 연산값의 범위는 long long이므로, stoll()을 사용한다.

ll calc(ll a, ll b, char c)
{
    switch(c)
    {
        case '*' : return a*b;
        case '/' : return a/b;
        case '+' : return a+b;
        case '-' : return a-b;
    }
}

<연산값 return 함수>
연산자의 종류에 따라 연산값을 return 한다.

void SOLVE()
{
    Parsing();

    //연산자가 없는 경우
    if(oper.empty()) cout << num[0];

    ll left = 0 , right = num.size()-1;
    while(!oper.empty())
    {
        //마지막 연산
        if(oper.size() == 1)
        {
            ll ans = calc(num[left],num[left+1],oper.front());
            cout << ans;
            return;
        }

        //왼쪽의 우선순위가 높은 경우
        if(oper1(oper.front()) && oper2(oper.back()))
        {
            num[left+1] = calc(num[left],num[left+1],oper.front());
            left++;
            oper.pop_front();
        }
            //오른쪽의 우선순위가 높은 경우
        else if(oper2(oper.front()) && oper1(oper.back()))
        {
            num[right-1] = calc(num[right-1],num[right],oper.back());
            right--;
            oper.pop_back();
        }
            //우선순위 같은 경우
        else
        {
            ll tempL = calc(num[left],num[left+1],oper.front());
            ll tempR = calc(num[right-1],num[right],oper.back());

            //앞의 연산값이 크거나 같은 경우 앞에 먼저
            if(tempL >= tempR)
                num[left+1] = tempL , left++ , oper.pop_front();
            else num[right-1] = tempR , right-- , oper.pop_back();
        }
    }
}

<알고리즘 진행 함수>
파싱 후 문제의 조건에 따라 연산을 진행한다.
연산자가 없는 경우의 예외 처리에 주의한다.
연산자가 한 개, 즉 deque의 크기가 1인 경우 마지막 연산을 의미하므로, 연산값 출력 후 프로그램을 종료한다.
연산을 진행할 때마다 left와 right의 증감에 주의한다.

🪄전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

string str;

typedef long long ll;
vector<ll> num;
deque<char> oper;

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> str;
}

bool oper1(char c)
{//mult or div
    return c=='*'||c=='/';
}
bool oper2(char c)
{//plus or minus
    return c=='+'||c=='-';
}

void Parsing()
{//수와 연산자 분리

    string token = "";
    for(int i = 0; i < str.length(); i++)
    {
        //연산자라면
        if(i && (oper1(str[i]) || oper2(str[i])))
            num.push_back(stoll(token)),
                    token = "",
                    oper.push_back(str[i]);
            //수라면
        else token += str[i];
    }num.push_back(stoll(token));
}

ll calc(ll a, ll b, char c)
{
    switch(c)
    {
        case '*' : return a*b;
        case '/' : return a/b;
        case '+' : return a+b;
        case '-' : return a-b;
    }
}

void SOLVE()
{
    Parsing();

    //연산자가 없는 경우
    if(oper.empty()) cout << num[0];

    ll left = 0 , right = num.size()-1;
    while(!oper.empty())
    {
        //마지막 연산
        if(oper.size() == 1)
        {
            ll ans = calc(num[left],num[left+1],oper.front());
            cout << ans;
            return;
        }

        //왼쪽의 우선순위가 높은 경우
        if(oper1(oper.front()) && oper2(oper.back()))
        {
            num[left+1] = calc(num[left],num[left+1],oper.front());
            left++;
            oper.pop_front();
        }
            //오른쪽의 우선순위가 높은 경우
        else if(oper2(oper.front()) && oper1(oper.back()))
        {
            num[right-1] = calc(num[right-1],num[right],oper.back());
            right--;
            oper.pop_back();
        }
            //우선순위 같은 경우
        else
        {
            ll tempL = calc(num[left],num[left+1],oper.front());
            ll tempR = calc(num[right-1],num[right],oper.back());

            //앞의 연산값이 크거나 같은 경우 앞에 먼저
            if(tempL >= tempR)
                num[left+1] = tempL , left++ , oper.pop_front();
            else num[right-1] = tempR , right-- , oper.pop_back();
        }
    }
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

정직한 구현 문제라 재미있게 풀었다. 시키는대로 코드만 작성하면 되는 뻔한 문제라는 생각이 들었지만, 푸는 시간이 짧지만은 않아 아쉬웠다.