[ 백준 15659 ] 연산자 끼워넣기(3) (C++)

백준의 연산자끼워넣기(3)(15659) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저, 이 문제는 연산자끼워넣기(1)과 같이, 주어진 N - 1개의 연산자들을 적절히 선택해서 최댓값 , 최솟값을 구해야 하는

문제이다. 달라진점이라면, 연산자에 우선순위가 존재한다는 것이다.

먼저, 계산은 뒤로 미뤄두고 연산자를 뽑는 과정에 대해서 생각해보자.

본인은 이 과정을 '중복순열'구현을 통해서 해결해보았다.

순서에 따라서 결과가 달라질 것이고 (1 + 2 * 3 과 1 * 2 + 3 의 결과는 다름) , 주어진 연산자의 갯수가 2개이상일 수 있으므로

중복적으로 선택을 해야만 한다. 따라서 이 과정을 중복순열을 통해서 구현해 주었다.

아직 중복순열에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 중복순열 알아보기(Click) ]

본인은 주어진 연산자들을 중복순열을 구현하는 코드로 구현하면서, 그 순서들을 벡터에 넣어주었다.

예제입력2 를 간단하게 예로 들어보겠다.

3 4 5 라는 주어진 식에

+ : 1개 , - : 0개 , * : 1개 , / : 0 개가 있는 상황이다.

그럼 중복순열로 뽑게된다면 아래와 같이 2가지 경우가 발생하게 된다.

[ + , * ] , [ * , + ]

이 순서를 벡터에 저장해 주었다는 의미이다.

이제 본격적으로 계산을 해보면 된다.

본인은 계산을 크게 2단계로 나누어 보았다.

1. 곱하기 연산자와 나누기 연산자를 계산하는 과정

2. 그 이후, 더하기 연산자와 빼기 연산자를 계산하는 과정

위에서 든 예제입력2를 통해서 예를 들어보면 다음과 같이 계산한다는 것이다.

3 4 5 에서 [ + , * ] 를 뽑은 경우를 보자.

이렇게 될 경우, 우리가 계산하고자 하는 전체 식을 적어보자면 " 3 + 4 * 5 " 가 될 것이다.

1번 단계에서는 위의 식을 " 3 + 20 " 으로 표현하는 과정이다.

2번 단계에서는 나머지 계산인 3 + 20 을 해서 최종적으로 답을 도출해내는 과정이다.

구체적인 계산 과정을 알아보기에 앞서, 어떻게 계산할 건지 전체적인 틀만 한번 알아보자.

1. 우리는 '연산자의 순서를 벡터에 저장' 해놨으므로, 이 순서만으로 원래의 식에 몇 번째 값을 계산해야 하는지

   알 수 있다.

- 조금 더 구체적으로 말해보자면, [ + , * ] 가 벡터에 순서대로 들어가있다고 생각해보자.

  즉, 벡터의 0번째 Index에는 + 가 들어가있고, 1번째 Index에는 * 가 들어가 있는 상태이다.

  그럼, 우리는 원래의 식에서 몇 번째 인덱스와 몇 번째 인덱스를 '+' 연산을 해야하고,

  몇 번째 인덱스와 몇 번째 인덱스를 '*' 연산을 해야할까 ??

  '+' 연산자는 0번에 존재하므로, 0번째 인덱스와 1번째 인덱스를 더해주면된다.

  '*' 연산자는 1번에 존재하므로, 1번째 인덱스와 2번째 인덱스를 곱해주면된다.

  즉, 우리는 몇 번째에 존재하는지 위치만으로 어떤 값들을 계산해줘야 하는지 알 수 있다.

  해당 연산자가 K번에 위치한다면, 원래 식의 K번 인덱스와 K + 1번 인덱스를 해당 연산자로 연산해주면 된다.

2. 결과를 자료형 String을 관리하는 Vector에 넣으면서 최종적인 식을 만들 것이다.

- 이 과정은 밑에서 진행하면서 설명하겠다. String 형을 관리하는 vector에 식을 만들어 넣을 것이라는 것 정도만 알고있자.

구체적으로 이 과정을 예제입력2 에서 발생하는 2가지 경우를 통해서 알아보자.

2가지 경우라는 것은

3 + 4 * 5 인 경우와

3 * 4 + 5 인 경우를 의미한다.

1. 곱하기 연산자와 나누기 연산자 계산하기

우선순위가 더 높은 연산자들이므로 우선적으로 계산이 되어줘야 하는 연산자들이다.

현재 벡터에는 '+' , '*' 순서로 존재한다고 가정하자.

즉, 우리가 계산하고자 하는 식은 3 + 4 * 5 인 것이다.

연산자가 존재하는 벡터들을 순차적으로 돌아보자.

첫 번째로 '+' 연산자가 나올 것이다. 그렇게되면, 우리는 2가지 경우에 대해서 처리를 해줘야 한다.

1. 기존에 아무런 숫자도 존재하지 않았던 경우

2. 기존에 어떤 숫자가 존재했던 경우

1번은 지금 하고자 하는 식인 '3 + 4 * 5' 와 같은 경우이다. 3 + 4 를 계산하기 전에, 그 전에는 이미 아무런 값도

계산된 적이 없다. 그럼 3 + 4 를 해버리면 될까 ? 아니다. 3 + (4 * 5) 이기 때문에, 실제로 4는 3 + 4로 묶이지 않는

숫자이다. 그리고 지금 우리가 하는 과정이 '곱하기 연산자와 나누기 연산자 계산' 하는 과정이다.

더하기와 빼기에 대해서는 계산을 하지 않는다. 따라서, 위의 숫자들을 그대로 string형 vector에 넣어주자.

그럼 아마 string형 벡터에는 다음과 같은 식이 들어가게 될 것이다.

[ "3" , "+" , "4" ]

2번째 경우는, 기존에 어떤 숫자가 존재했던 경우이다.

위의 예시에서 든, 3 * 4 + 5 인 경우이다.

이 경우에 '+' 를 만나게 되도, 그 전에 이미 계산된 12(3 * 4) 가 존재한다.

따라서, 이 경우에는 K번째 Index와 K + 1번째 Index에 존재하는 숫자들을 연산하는 것이 아니라,

기존의 숫자와, K + 1번째 Index에 존재하는 숫자를 연산해주어야 한다.

기존의 숫자는 이미 Vector에 들어가 있을 것이므로, 이 경우에는 '+' 연산자와, K + 1번째 Index의 숫자만 Vector에

넣어주자.

여기까지 진행했다면 우리가 식을 생성하기 위해 사용한 Vector에는 어떤 값들이 들어가 있을까 ??

3 + 4 * 5 의 경우, 벡터에는 [ "3" , "+" , "20" ] 이 존재하게 될 것이다.

3 * 4 + 5 의 경우, 벡터에는 [ "12" + "5" ] 가 존재하게 될 것이다.

이제는 위의 식을 그대로 앞에서부터 순차적으로 계산만 해주면 된다.

왜냐하면, 곱하기와 나누기에 대한 우선적인 계산이 끝났으므로, 남아있는 연산자는 "+"와 "-" 밖에 없다.

이 2개의 연산자간에는 우선순위가 존재하지 않으므로 순차적으로 계산을 하면 된다.

말로 설명하니 되게 어려운 것 같다. 코드를 통해서 라인별로 어떻게 구현되고 동작되는지 간단하게 알아보고

전체 소스코드를 참고하도록 하자.

void Calculate()
{
    vector<string> String;
 
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i] == 0 || V[i] == 1)
        {
            if (String.size() >= 1)
            {
                String.push_back(Oper_To_Str(V[i]));
                String.push_back(to_string(Arr[i + 1]));
            }
            else
            {
                String.push_back(to_string(Arr[i]));
                String.push_back(Oper_To_Str(V[i]));
                String.push_back(to_string(Arr[i + 1]));
            }
        }
        else
        {
            if (String.size() >= 1)
            {
                int Num = stoi(String[String.size() - 1]);
                int Res = Calc(Num, Arr[i + 1], V[i]);
                String.pop_back();
                String.push_back(to_string(Res));
            }
            else
            {
                int Res = Calc(Arr[i], Arr[i + 1], V[i]);
                String.push_back(to_string(Res));
            }
        }
    }
 
    int Result = 0;
    Result = stoi(String[0]);
    for (int i = 1; i < String.size(); i = i + 2)
    {
        if (String[i] == "+") Result = Result + stoi(String[i + 1]);
        else if(String[i] == "-") Result = Result - stoi(String[i + 1]);
    }
}

이게 본인이 구현한 계산하는 코드이다.

위에서 사용된 벡터 'V'에는 연산자의 순서가 저장되어 있다.

우리는 식을 String Vector에 넣어가면서 만들 것이다.

line7) 의 경우 '+' '-' 연산자를 만난 경우이다.

위에서 말했듯이, 이 경우에 2가지 경우로 나뉘게 된다.

line9) 기존에 다른 숫자가 이미 존재하는 경우

line14) 기존에 다른 숫자가 존재하지 않는 경우

line10 - 12) 를 보게 되면, 기존에 다른 숫자가 존재한 경우에는 위에서 말했듯이, 기존의 숫자와, K + 1번쨰 인덱스의

숫자를 계산해 줘야 하므로, 연산자와, K + 1번째 숫자만 넣어주는 것을 확인할 수 있다.

line16 - 18)을 보게되면, 기존에 다른 숫자가 존재하지 않은 경우이므로, K번째 숫자와, 연산자, K + 1번째 숫자를 넣어준다.

절대로 +, -에 대해서는 먼저 계산하지 않고 식에 그대로 넣어준다.

line21)의 경우 '*'와 '/' 연산자를 만난 경우이다. 우선적으로 계산을 해줘야 한다는 것이다.

이 경우도, 더하기 뺴기와 같이 2가지 경우로 나뉜다.

기존에 숫자가 존재한 경우와 존재하지 않은 경우

line30 - 34)를 보게되면, 기존에 숫자가 존재하지 않은 경우를 구현한 것이다.

K번째, K + 1번째의 값을 바로 계산을 해서 String vector에 넣어준다.

line23 - 28)은 기존에 숫자가 존재한 경우이다. 이 경우에 우리는 값을 하나 뺴주는 연산을 해줘야 한다.

"3 + 4 * 5" 의 경우를 생각해보자. 첫 번째 나온 연산자인 '+' 에 의해서 String Vector에는 [ "3" , "+" , "4" ] 가 존재하는

상태일 것이다. 이 때, 곱하기를 만나게 되면 ?? 벡터에 존재하는 가장 마지막 값과, K + 1번째의 값을 연산해 주어야 한다.

즉, 위의 상태에서는 '4'와, K+1번째 값인 '5'가 계산 되어야 한다는 것이다.

그럼, 이제 '4'는 이미 계산된 숫자이므로 더 이상 최종 식에 존재해서는 안되는 숫자이다.

따라서, 하나의 값을 빼주고, 연산 한 후에, 그 결과값을 String Vector에 넣어주자 !

line38 - 44) 는 최종적으로 나머지 계산인 더하기와 빼기 과정을 계산해주는 과정이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<string>
 
#define endl "\n"
#define MAX 15
using namespace std;
 
int N;
int Arr[MAX];
int Oper[4];
bool Select[MAX];
int Big_Answer = -2e9;
int Min_Answer = 2e9;
vector<int> V;
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++) cin >> Arr[i];
    for (int i = 0; i < 4; i++) cin >> Oper[i];
}
 
string Oper_To_Str(int op)
{
    if (op == 0) return "+";
    else if (op == 1) return "-";
    else if (op == 2) return "*";
    else if (op == 3) return "/";
}
 
int Calc(int x, int y, int oper)
{
    string c = Oper_To_Str(oper);
    if (c == "+") return x + y;
    else if (c == "-") return x - y;
    else if (c == "*") return x * y;
    else if (c == "/") return x / y;
}
 
void Calculate()
{
    vector<string> String;
 
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i] == 0 || V[i] == 1)
        {
            if (String.size() >= 1)
            {
                String.push_back(Oper_To_Str(V[i]));
                String.push_back(to_string(Arr[i + 1]));
            }
            else
            {
                String.push_back(to_string(Arr[i]));
                String.push_back(Oper_To_Str(V[i]));
                String.push_back(to_string(Arr[i + 1]));
            }
        }
        else
        {
            if (String.size() >= 1)
            {
                int Num = stoi(String[String.size() - 1]);
                int Res = Calc(Num, Arr[i + 1], V[i]);
                String.pop_back();
                String.push_back(to_string(Res));
            }
            else
            {
                int Res = Calc(Arr[i], Arr[i + 1], V[i]);
                String.push_back(to_string(Res));
            }
        }
    }
 
    int Result = 0;
    Result = stoi(String[0]);
    for (int i = 1; i < String.size(); i = i + 2)
    {
        if (String[i] == "+") Result = Result + stoi(String[i + 1]);
        else if(String[i] == "-") Result = Result - stoi(String[i + 1]);
    }
 
    if (Result > Big_Answer) Big_Answer = Result;
    if (Result < Min_Answer) Min_Answer = Result;
}
 
void DFS(int Cnt)
{
    if (Cnt == N - 1)
    {
        Calculate();
        return;
    }
 
    for (int i = 0; i < 4; i++)
    {
        if (Oper[i] >= 1)
        {
            Oper[i]--;
            V.push_back(i);
            DFS(Cnt + 1);
            V.pop_back();
            Oper[i]++;
        }
    }
}
 
void Solution()
{
    DFS(0);
    cout << Big_Answer << endl << Min_Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}