반응형
해결 방법
(i) 문자열을 파싱하여 정수 부분과 연산자 부분을 따로 추출하여 벡터에 저장한다.
(ii) 우선 순위를 배정한다. 우선순위에 대한 경우의 수는 6이기 때문에 6가지 경우만 시뮬레이션 하면 된다.
(iii) 남아 있는 연산자들 중 가장 우선 순위가 높은 연산자를 찾아서, 해당 연산자에 대한 연산을 수행한다.
(iv) 연산 결과는 합쳐서 정수 벡터에 반영하고, 사용한 연산자는 연산자 벡터에서 제거하고, 남은 해당 연산자 카운트를 1 감소시킨다. 이렇게 하면 연산마다 정수 벡터와 연산자 벡터의 크기는 각각 1씩 줄어들 것이고, 모든 연산을 수행했을 때는 정수 결과값 하나만 남게 된다.
(v) 모든 경우에 대한 정수 결과값들의 최댓값을 구한다.
소스 코드
#include <string>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
vector<long long> nv, nvc; // 정수 부분 추출
vector<char> no, noc; // 연산자 부분 추출
int opern[3]; // +, -, * 연산자 개수
map<char, int> m;
int prior[6][3]={{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
long long cal(long long a, long long b, char c) {
if(c=='+') return (long long)(a+b);
else if(c=='-') return (long long)(a-b);
else return (long long)(a*b);
}
long long solution(string expression) {
long long answer = 0;
int p=0;
//문자열 파싱
for(int i=0;i<expression.length();i++){
if(expression[i]=='+'||expression[i]=='-'||expression[i]=='*'){
nv.push_back(stoi(expression.substr(p, i-p)));
no.push_back(expression[i]);
p=i+1;
}
}
nv.push_back(stoi(expression.substr(p)));
// 우선순위에 대한 모든 경우를 탐색
for(int i=0;i<6;i++){
long long cal_result, highest_priority;
m['+']=prior[i][0]; m['-']=prior[i][1]; m['*']=prior[i][2]; // 우선 순위 부여
nvc.resize(nv.size()); copy(nv.begin(), nv.end(), nvc.begin());
noc.resize(no.size()); copy(no.begin(), no.end(), noc.begin());
memset(opern, 0, sizeof(opern));
for(int j=0;j<noc.size();j++) opern[m[noc[j]]]++; // 각 연산자 수 카운트
while(!noc.empty()){
for(int j=0;j<3;j++){ // 남아 있는 연산자들 중 우선순위가 가장 큰 연산자를 탐색
if(opern[j]) {
highest_priority=j;
break;
}
}
for(int j=0;j<noc.size();j++){ // 우선순위가 가장 큰 연산자에 대한 연산을 수행
if(m[noc[j]]==highest_priority){
cal_result=cal(nvc[j], nvc[j+1], noc[j]);
nvc[j]=cal_result;
nvc.erase(nvc.begin()+j+1, nvc.begin()+j+2);
noc.erase(noc.begin()+j, noc.begin()+j+1);
opern[highest_priority]--;
break;
}
}
}
nvc[0]=(nvc[0]>0)?nvc[0]:nvc[0]*(-1);
answer=max(answer, nvc[0]);
}
return answer;
}
테스트케이스 30개 모두 통과
반응형
'Algorithm > 기타 알고리즘' 카테고리의 다른 글
[집합] 뉴스 클러스터링 - 2018 KAKAO BLIND RECRUITMENT (0) | 2022.05.24 |
---|---|
[Linked List] 표 편집 - 2021 카카오 채용연계형 인턴십 (0) | 2022.05.22 |
[구간합] 쿠키 구입 - Summer/Winter Coding(~2018) (0) | 2022.05.01 |
[시뮬레이션] 스킬트리 - Summer/Winter Coding(~2018) (0) | 2022.04.29 |
[수학] 멀쩡한 사각형 - Summer/Winter Coding(2019) (0) | 2022.04.22 |
댓글