프로그래머스의 수식최대화(Lv2) 문제이다.

 

[ 문제풀이 ]

주어진 수식에서 연산자들에게 우선순위를 부여한 후에 절대값의 크기가 가장 큰 값을 구해야 하는 문제이다.

주어진 수식을 어떻게 관리할지부터 정답을 도출하는 과정까지 단계별로 진행해보자.

 

#1. 숫자와 연산자의 분리

본인은 가장 먼저 주어진 수식을 이용해서 숫자와 연산자를 분리해 주었다.

한 가지 예를 들어보자. 문제에서 2번 입출력 예로 주어진 케이스를 예시로 가져와보자.

"50 * 6 - 3 * 2" 라는 수식이 주어진다.

그럼 본인은 이를 다음과 같이 2개의  Vector를 생성해서 숫자와 연산자들을 분리해 주었다.

숫자를 저장하는 Vector = { 50 , 6 , 3 , 2 }

연산자를 저장하는 Vector = { * , - , * }

이와 같이 순차적으로 숫자와 연산자들을 각각 저장해 주었다.

이렇게 나눠서 저장하였을 때, 계산을 하는 과정에 대해서는 아래쪽에서 더욱 구체적으로 이야기를 해보도록 하자.

이 부분을 소스코드로 다음과 같이 구현해 보았다.

vector<char> Operator;
vector<long long> Number;
map<int, char> Oper_Type;

void Setting(string Str)
{
	Oper_Type[0] = '*';
	Oper_Type[1] = '+';
	Oper_Type[2] = '-';

	string Num = "";
	for (int i = 0; i < Str.length(); i++)
	{
		if (isdigit(Str[i]) == 0)
		{
			Number.push_back(stoll(Num));
			Operator.push_back(Str[i]);
			Num = "";
		}
		else Num += Str[i];
	}
	Number.push_back(stoll(Num));
}

위의 코드에서 Oper_Type 이라고 불리는 map이 하나 선언되어 있다. 이 map은 연산자 기호들을 단순히 숫자로 표현하기 위해서 숫자를 연산자 기호로 mapping 시키기 위해서 사용한 것이다. 이 map의 활용도에 대해서도 아래쪽에서 구체적으로 이야기 해보도록 하자.

 

#2. 우선순위 정하기

계산을 하기에 앞서서 연산자들의 우선순위를 정하는 과정에 대해서 알아보자.

본인은 이 부분을 순열을 통해서 구현해보았다. 순열을 구현함으로써, 주어진 순서에 따라서 우선순위를 부여하면 되어버리기 때문이다. 순열은 딱 3개의 값에 대해서만 구현해 주었다.

어차피 연산자가 + , - , * 3개밖에 없기 때문에 이 3개에 대해서 순열을 구현해 주었다.

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

[ 순열 알아보기 (Click) ]

 

소스코드로 나타내면 다음과 같다.

long long Answer;
bool Select[3];
vector<char> Priority;
vector<long long> Number;
map<int, char> Oper_Type;

void DFS(int Cnt)
{
	if (Cnt == 3)
	{
		long long Result = Find_Result();
		Answer = Max(Answer, Result);
		return;
	}

	for (int i = 0; i < 3; i++)
	{
		if (Select[i] == true) continue;
		Select[i] = true;
		Priority.push_back(Oper_Type[i]);
		DFS(Cnt + 1);
		Priority.pop_back();
		Select[i] = false;
	}
}

위의 코드에서 순열을 구하는 for문을 보게되면 2가지 의문점이 들 수도 있다.

1. 0~2 사이의 값들을 이용해서 순열을 구하는데, 이를 통해서 + , - , * 를 어떻게 표현할 수 있을까 ??

이 과정을 위해서 #1에서 map을 선언해 준 것이다. int형 데이터들을 통해서 char형 데이터인 +, - , *를 표현할 수 있도록 매핑시켜놓은 과정이라고 생각하면 된다.

따라서, 실제로 순열을 구할때에는 단순히 숫자 0 ~ 2 에 대한 순열만 구해주면 된다.

2. 만약, 연산자가 3개가 없는 경우에는 어떻게 될까 ??

"50 * 6 - 3 * 2" 이 예시만 보더라도, 주어진 연산자가 * 와 - 2개밖에 존재하질 않는다.

그런데 ! 위와 같이 3개에 대한 순열을 구한다면 문제가 발생하지 않을까 ??

결과적으로 말하자면 문제가 발생하지는 않는다. 사실 더욱 정확하게 하려면, 기존에 주어진 수식에서 존재하는 연산자가 무엇이 있고, 몇 개가 있는지 파악한 후에 존재하는 갯수만큼만 탐색을 하면 더욱 정확할 것이다.

그런데 사실, 그런과정이 큰 의미가 없다고 생각을 했고, 2개에 대한 순열이나 3개에 대한 순열이나 시간적으로 차이가 많이 나는 것도 아니기 때문에 그냥 본인은 편하게 3개에 대한 우선순위를 정해주었다.

연산 결과에 영향을 미치지 않는다는 것은 밑에서 계산하는 과정에서 구체적으로 이야기해보자.

 

#3. 계산하기

지금까지 했던 과정들을 이야기해보자.

1. 숫자와 연산자를 분리해 놓았다.

2. 연산자들의 우선순위를 정해주었다.

이제 실제로 계산하는 일만 남아있다 ! 예시를 가지고 진행을 해보자.

"50 * 6 - 3 * 2"

그리고 현재 우선순위가 [ + , * , - ] 로 이루어져 있다고 가정해보자. + 가 가장 우선순위가 높아서 가장 먼저 계산이 되어야 할 상황인 것이다.

숫자의 Vector = [ 50 , 6 , 3 , 2 ]

연산자의 Vector = [ * , - , * ]

 

가장 먼저, '+'가 계산되어야 하므로 주어진 연산자 Vector에서 '+'를 찾아보자. 찾아보니 존재하지 않는다. 따라서 그냥 넘어가버리면 된다.

 

두 번째로, '*'가 계산되어야 하므로 주어진 연산자 Vector에서 '*'를 찾아보자.

찾아보니, 0번 Index 에서 '*'를 찾을 수가 있다.

그렇다면 , 0번 Index에 존재하는 '*' 연산자는 숫자 Vector에서 어떤 값과 어떤 값을 계산하는데 사용되는 연산자일까 ?

바로 , 50 과 6 을 곱하는데 사용되는 연산자이다. 50 과 6은 다시 이야기해서, 숫자 Vector에서 Index번호가 0번인 데이터와 1번인 데이터이다.

즉 ! 찾으려는 연산자를 연산자 Vector에서 찾았다면, 해당 연산자가 가지고 있는 Index번호를 통해서 "숫자 Vector의 Index번호 데이터와 Index번호 + 1 번째 데이터를 계산" 을 하면 되는 것이다.

그럼, 우리는 여기서 50 * 6 = 300 이라는 값을 얻을 수 있을 것이다.

그리고 나서는 숫자와 연산자 Vector를 정리를 해줄 것이다.

바로, 숫자의 Vector = [ 300 , 3 , 2 ] 가 되도록, 그리고 연산자 Vector = [ - , * ] 가 되도록 정리를 해줄 것이다.

즉 ! 계산한 데이터들은 바로바로 지워버리는 것이다.

Vector에서는 erase()함수를 이용해서 데이터를 쉽게 지워버릴 수가 있다. 그런데 ! 이 erase() 함수를 사용할 때 주의해야 할 것이 하나 있다. 바로, 모든 데이터의 Index번호가 땡겨진다는 것이다.

예를 들어서 Vector에 [ 1 , 2 , 3 , 4 , 5 ] 가 있는데 여기서 1번 Index 데이터를 지워버렸다고 가정해보자.

그럼 숫자 '2'가 지워질 것이다. 그럼 Vector는 [ 1 , 3 , 4 , 5 ] 가 될 것인데, 이 때 '3' , '4' , '5' 데이터들을 보게 되면 Index번호가 하나씩 감소했다는 것을 알 수 있다. 이 부분을 위해서 탐색하고 있는 포인터의 값을 감소시키는 과정이 필요하다. 이 부분은 코드를 확인하고 다시 이야기를 해보자.

 

그 이후에 탐색을 계속해서 또 '*' 연산자를 찾아봤더니, 1번 Index에 *연산자가 존재한다. 왜냐하면, 첫 번째 *가 연산자 Vector에서 사라졌으므로 Index번호가 하나씩 감소했으므로 1번 Index에 * 연산자가 존재하는 것이다.

1번 Index에서 연산자를 찾았다면 ? 숫자 Vector에서 1번 Index와 1 + 1번 Index의 데이터를 계산을 해주면 된다.

즉, 숫자 Vector = [ 300 , 3 , 2 ] 에서 1번과 2번 Index의 데이터를 계산해보면 [ 300 , 6 ] 이 될 것이다.

그 이후에 '-'를 찾아서 연산을 하게 되면 결과적으로 300 - 6 을 계산하게 되고, 숫자의 Vector에는 [ 294 ] 만 남아있을 것이다. 즉 ! 우리가 찾고자 하는 결과값은 숫자 Vector의 0번 Index에 최종적으로 남아있게 된다.

코드로 확인해보자.

long long Calculate(long long N1, long long N2, char Op)
{
	if (Op == '*') return N1 * N2;
	if (Op == '+') return N1 + N2;
	if (Op == '-') return N1 - N2;
}

long long Find_Result()
{
	vector<char> Temp_Operator = Operator;
	vector<long long> Temp_Number = Number;
	for (int i = 0; i < 3; i++)
	{
		char C = Priority[i];
		for (int j = 0; j < Temp_Operator.size(); j++)
		{
			if (Temp_Operator[j] == C)
			{
				long long Result = Calculate(Temp_Number[j], Temp_Number[j + 1], C);
				Temp_Number[j] = Result;
				Temp_Number.erase(Temp_Number.begin() + j + 1);
				Temp_Operator.erase(Temp_Operator.begin() + j);
				j--;
			}
		}
	}
	return abs(Temp_Number[0]);
}

line 17) 에서 J번 Index에서 현재 계산하고자 하는 연산자를 찾았다면, J번과 J + 1번 Index에 존재하는 숫자들이 계산을 하게 된다.

숫자 Vector = [ 50 , 6 , 3 , 2 ]

연산자 Vector = [ * , - , * ]

이 상태에서, 계산을 하고 난 후에 숫자 Vector를 [ 300 , 3 , 2 ]로 만들어주는 과정이 line20 ~21) 의 과정이다.

J번 Index는 결과값으로 바꿔버리고, J + 1번 Index는 삭제를 시켜버리는 것이다.

연산자 Vector를 [ - , * ] 로 만들어 버리는 과정은 line 22) 에 존재한다. J번 Index의 값을 삭제시켜 버리는 것이다.

하지만 ! 중요한 점은 여기서 모든 데이터의 Index값이 하나씩 땡겨지기 때문에 포인터를 한 칸 감소시켜 줘야 한다는 과정이 필요하다고 했었다. 그 과정이 line 23)에 있는 J-- 부분이라고 볼 수 있다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
 
long long Answer;
bool Select[3];
vector<char> Operator, Priority;
vector<long long> Number;
map<int, char> Oper_Type;
 
long long Max(long long A, long long B) { return A > B ? A : B; }
 
void Setting(string Str)
{
    Oper_Type[0] = '*';
    Oper_Type[1] = '+';
    Oper_Type[2] = '-';
 
    string Num = "";
    for (int i = 0; i < Str.length(); i++)
    {
        if (isdigit(Str[i]) == 0)
        {
            Number.push_back(stoll(Num));
            Operator.push_back(Str[i]);
            Num = "";
        }
        else Num += Str[i];
    }
    Number.push_back(stoll(Num));
}
 
long long Calculate(long long N1, long long N2, char Op)
{
    if (Op == '*') return N1 * N2;
    if (Op == '+') return N1 + N2;
    if (Op == '-') return N1 - N2;
}
 
long long Find_Result()
{
    vector<char> Temp_Operator = Operator;
    vector<long long> Temp_Number = Number;
    for (int i = 0; i < 3; i++)
    {
        char C = Priority[i];
        for (int j = 0; j < Temp_Operator.size(); j++)
        {
            if (Temp_Operator[j] == C)
            {
                long long Result = Calculate(Temp_Number[j], Temp_Number[j + 1], C);
                Temp_Number[j] = Result;
                Temp_Number.erase(Temp_Number.begin() + j + 1);
                Temp_Operator.erase(Temp_Operator.begin() + j);
                j--;
            }
        }
    }
    return abs(Temp_Number[0]);
}
 
void DFS(int Cnt)
{
    if (Cnt == 3)
    {
        long long Result = Find_Result();
        Answer = Max(Answer, Result);
        return;
    }
 
    for (int i = 0; i < 3; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        Priority.push_back(Oper_Type[i]);
        DFS(Cnt + 1);
        Priority.pop_back();
        Select[i] = false;
    }
}
 
long long solution(string expression)
{
    Setting(expression);
    DFS(0);
    return Answer;
}
 cs

 

 

 

저작자표시

'[ Programmers Code ] > # PG - Level2' 카테고리의 다른 글

[ 프로그래머스 124 나라의 숫자 (Lv2) ] (C++)  (7) 2021.08.12
[ 프로그래머스 후보키 (Lv2) ] (C++)  (4) 2021.07.21
[ 프로그래머스 거리두기 확인하기 (Lv2) ] (C++)  (2) 2021.07.15
[ 프로그래머스 행렬 테두리 회전하기 (Lv2) ] (C++)  (0) 2021.07.02
[ 프로그래머스 [ 3차 ] 압축 (Lv2) ] (C++)  (0) 2021.06.30

+ Recent posts

티스토리툴바