문제 링크입니다: https://www.acmicpc.net/problem/16638
백준 16637번 괄호 추가하기(https://jaimemin.tistory.com/1454) 와는 다르게 연산자 우선순위가 다른 문제였습니다.
하지만 여전히 중첩괄호는 허용하지 않다보니 수월하게 풀 수 있는 문제였습니다.
아이디어는 자료구조 시간에 배운 후위연산식 만드는 과정과 계산하는 방법에서 얻었으며
이에 대한 내용은 아래 링크를 참고하시면 됩니다!
https://jaimemin.tistory.com/158
알고리즘은 아래와 같습니다.
1. 우선순위를 설정하는데 왼쪽 괄호를 제일 높게, *를 그 다음, 그리고 +와 -는 제일 낮게 부여합니다.
2. func 함수를 호출하고 [idx, N) 범위 내 반복문을 돌립니다.
2.1 범위 내 피연산자 2개와 연산자 1개가 있을 수 없어 괄호로 묶을 수 없을 경우 별 다른 조치 없이 다음 인덱스에 대해 재귀함수를 호출합니다.
2.2 범위 내 피연산자 2개와 연산자 1개가 있고 괄호로 묶을 수 있을 경우 ([i 번째 인덱스] 연산자 [(i + 2) 번째 인덱스]) 와 같이 묶고 재귀함수를 호출합니다.
3. 문자열 s의 인덱스 범위를 벗어났다면 괄호를 다 묶었다고 가정하고 후위연산식 계산을 시작합니다.
3.1 현재까지 구한 최대값과 비교하여 최대값을 갱신해줍니다.
#include <iostream> | |
#include <string> | |
#include <algorithm> | |
#include <stack> | |
#include <cstring> | |
#include <climits> | |
#include <map> | |
using namespace std; | |
const int MAX = 20; | |
int N; | |
int result = INT_MIN; | |
string s; | |
map<char, int> priority; | |
char parenthesis[MAX]; | |
void setPriority(void) | |
{ | |
priority['('] = 2; | |
priority['*'] = 1; | |
priority['+'] = 0; | |
priority['-'] = 0; | |
} | |
bool isNotParenthesis(int idx) | |
{ | |
return (parenthesis[idx] != '(' && parenthesis[idx] != ')'); | |
} | |
bool isOperand(char c) | |
{ | |
return (c >= '0' && c <= '9'); | |
} | |
int calculate(int a, int b, char op) | |
{ | |
switch (op) | |
{ | |
case '+': | |
return a + b; | |
case '-': | |
return a - b; | |
case '*': | |
return a * b; | |
} | |
} | |
int calculatePostfix(string tempS) | |
{ | |
stack<int> postfixStack; | |
for (int i = 0; i < tempS.size(); i++) | |
{ | |
if (isOperand(tempS[i])) | |
{ | |
postfixStack.push(tempS[i] - '0'); | |
continue; | |
} | |
if (postfixStack.size() >= 2) | |
{ | |
int second = postfixStack.top(); | |
postfixStack.pop(); | |
int first = postfixStack.top(); | |
postfixStack.pop(); | |
int temp = calculate(first, second, tempS[i]); | |
postfixStack.push(temp); | |
} | |
} | |
return postfixStack.top(); | |
} | |
int postfixResult() | |
{ | |
string tempS; | |
stack<char> st; | |
for (int i = 0; i < N; i++) | |
{ | |
if (isOperand(s[i])) | |
{ | |
tempS += s[i]; | |
} | |
switch (parenthesis[i]) | |
{ | |
case '(': | |
st.push('('); | |
break; | |
case ')': | |
while (st.empty() == false && st.top() != '(') | |
{ | |
tempS += st.top(); | |
st.pop(); | |
} | |
st.pop(); | |
break; | |
default: | |
if (isOperand(s[i])) | |
{ | |
break; | |
} | |
while (st.empty() == false && priority[st.top()] >= priority[s[i]]) | |
{ | |
if (st.top() == '(') | |
{ | |
break; | |
} | |
tempS += st.top(); | |
st.pop(); | |
} | |
st.push(s[i]); | |
break; | |
} | |
} | |
while (st.empty() == false) | |
{ | |
tempS += st.top(); | |
st.pop(); | |
} | |
return calculatePostfix(tempS); | |
} | |
void func(int idx) | |
{ | |
if (idx >= N) | |
{ | |
result = max(result, postfixResult()); | |
return; | |
} | |
for (int i = idx; i < N; i += 2) | |
{ | |
if (i >= N - 2) | |
{ | |
func(i + 1); | |
continue; | |
} | |
if (isNotParenthesis(i) && isNotParenthesis(i + 2)) | |
{ | |
parenthesis[i] = '('; | |
parenthesis[i + 2] = ')'; | |
func(i + 2); | |
parenthesis[i] = ' '; | |
parenthesis[i + 2] = ' '; | |
} | |
} | |
} | |
int main(void) | |
{ | |
ios_base::sync_with_stdio(0); | |
cin.tie(0); | |
cin >> N; | |
cin >> s; | |
setPriority(); | |
func(0); | |
cout << result << "\n"; | |
return 0; | |
} |
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 16639번 괄호 추가하기 3 (2) | 2020.05.26 |
---|---|
백준 1408번 24 (0) | 2020.05.26 |
백준 16637번 괄호 추가하기 (6) | 2020.05.24 |
백준 1019번 책 페이지 (0) | 2020.05.22 |
백준 13904번 과제 (0) | 2020.05.21 |