1. 문제
https://school.programmers.co.kr/learn/courses/30/lessons/67257
[제한 사항]
- expression은 길이가 3 이상 100 이하인 문자열입니다.
- expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
- 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
- expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
- -즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
- "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
expression은 적어도 1개 이상의 연산자를 포함하고 있습니다. - 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 263 - 1 이하가 되도록 입력이 주어집니다.
- 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.
[입출력 예]
| expression | result |
|---|---|
| "100-200*300-500+20" | 60420 |
| "506-32" | 300 |
2. 풀이
2-1. [완전탐색] 풀이
경우의 수가 많지 않을때는 직접 모든 경우의 수를 나열하는 것이 빠를 수 있음.
✨핵심 Point
StringTokenizer st = new StringTokenizer(expression, "-+*", true); while(st.hasMoreTokens()) { list.add(st.nextToken()); }
📌계산하는 부분에서 i -= 2를 하는 이유
ex) 10 + 20 - 100
여기서 연산자 +를 만난 부분이 i(=1번째 인덱스)이라고 하면 remove i - 1을 3번 해서 결과를 i - 1에 넣어주면
30 - 100이 되고, 이때 i는 여전히 1번째 인덱스이다. 위 for문을 돌아가서 i++ 을 해주기 때문에 따라서 i - 2를 해주고, 다시 30부터 가리키도록 설정하는 것이다.for(String opS : op){ for(int i = 0; i < calList.size(); i++){ if(calList.get(i).equals(opS)){ long resultTmp = calculate(calList.remove(i-1), calList.remove(i-1), calList.remove(i-1)); calList.add(i-1, String.valueOf(resultTmp)); i -= 2; } } }
2-2. [DFS] 풀이
전체 경우를 DFS로 고려하여 풀이.
3. 전체 코드
3-1. [완전탐색] 코드
import java.util.*;
class Solution {
String[][] operator = {{"*", "+", "-"}, {"*", "-", "+"},
{"+", "*", "-"}, {"+", "-", "*"},
{"-", "*", "+"}, {"-", "+", "*"}};
public long solution(String expression) {
StringTokenizer st = new StringTokenizer(expression, "*+-", true);
ArrayList<String> list = new ArrayList<>();
while(st.hasMoreTokens()){
list.add(st.nextToken());
}
long max = 0;
for(String op[] : operator){
long result = calculate(new ArrayList<>(list), op);
if(max < result){
max = result;
}
}
return max;
}
public long calculate(ArrayList<String> calList, String op[]){
for(String opS : op){
for(int i = 0; i < calList.size(); i++){
if(calList.get(i).equals(opS)){
long resultTmp = calculate(calList.remove(i-1), calList.remove(i-1), calList.remove(i-1));
calList.add(i-1, String.valueOf(resultTmp));
i -= 2;
}
}
}
return Math.abs(Long.parseLong(calList.get(0)));
}
public long calculate(String a, String c, String b){
long al = Long.parseLong(a);
long bl = Long.parseLong(b);
if(c.equals("+")){
return al + bl;
} else if(c.equals("-")){
return al - bl;
} else{
return al * bl;
}
}
}3-2. [DFS] 전체코드
import java.util.*;
class Solution {
static char opers [] = {'+', '-', '*'};
static int check [] = new int [3];
static ArrayList<Long> Numbers = new ArrayList<>();
static ArrayList<Character> Ops = new ArrayList<>();
static ArrayList<Long> Answer = new ArrayList<>();
public long solution(String expression) {
long answer = 0;
String add_num = ""; // charAt으로 100 = 1 + 0 + 0
for(int ex = 0; ex < expression.length(); ex++) {
if(expression.charAt(ex) >= '0' && expression.charAt(ex) <= '9') {
add_num = add_num + expression.charAt(ex);
}
else {
Numbers.add(Long.parseLong(add_num)); // 숫자 넣기
Ops.add(expression.charAt(ex)); // 연산자 집어넣어주기
add_num = ""; // 문자열을 초기화 해줘야 다음 숫자를 받는다
}
}
Numbers.add(Long.parseLong(add_num)); // 맨 마지막 숫자 넣기.
dfs(0, new char [3]);
answer = Collections.max(Answer);
return answer;
}
public static void dfs(int count, char[] p) {
if(count == 3) {
ArrayList<Long> tmp_Numbers = new ArrayList<>(Numbers);
ArrayList<Character> tmp_Ops = new ArrayList<>(Ops);
for(int pp = 0; pp < p.length; pp++) {
for(int i = 0; i < tmp_Ops.size(); i++) {
// 연산자 배열안에 있는게 지금 우선순위에 있는거랑 같다면
if(tmp_Ops.get(i) == p[pp]) {
Long tmp_result = Cal(tmp_Numbers.remove(i), tmp_Numbers.remove(i), p[pp]);
tmp_Numbers.add(i, tmp_result);
tmp_Ops.remove(i); // 연산자 제거
i--;
}
}
}
Answer.add(Math.abs(tmp_Numbers.get(0))); // 절대값 변환.
return; // 종료.
}
for(int i = 0; i < opers.length; i++) {
if(check[i] == 0) { // 아직 방문을 하지 않는 곳이면
check[i] = 1; // 방문 체크
p[count] = opers[i];
dfs(count+1, p);
check[i] = 0; // 체크 해제
}
}
}
public static Long Cal(Long a, Long b, char c) {
long jump_this_ops = 0;
if(c == '+')
return a + b;
else if(c == '-')
return a - b;
else if(c == '*')
return a * b;
else
return jump_this_ops;
}
}
Hi!