들어가는 말
연산자의 우선순위를 정해서 가장 큰 계산 값을 반환하는 문제다.
기본적으로 dfs를 이용해서 연산자의 순서를 정한 다음에 스텍을 이용해 후위 수식 계산을 하면 된다고 생각했다.
위의 아이디어로 풀었지만 자잘한 오류들 때문에 시간이 많이 걸렸다.
String과 Character을 구분하는 것과 숫자가 한 자릿수 이상이 때문에 리스트를 이용하는 것 계산 값이 커지는 것을 대비해 long형 이용하기, 스텍은 후입선출로 빼기를 해줄 때는 second - first 같은.
코드 설명
먼저 리스트에 숫자와 연산자를 넣어줘야 한다.
그냥 문자열로 숫자를 사용할 경우 숫자가 한 자릿수 이상이기 때문에 원하는 값이 나오지 않을 수 있다.
//연산자와 숫자를 따로 리스트에 넣어준다.
for(int i=0; i<expression.length(); i++){
if(expression.charAt(i) == '+' || expression.charAt(i) == '-' || expression.charAt(i) == '*'){
list.add(num);
list.add(Character.toString(expression.charAt(i)));
num = "";
}else{
num += expression.charAt(i);
}
}
list.add(num);그리고 dfs를 이용해서 각 연산자의 우선순위를 정해준다.
우선순위 배열이 다 만들어지면 먼저 있는 것을 제일 큰 우선순위로 마지막에 있는 것을 제일 작은 우선순위로 정해서 map에 넣어준다.
public static void dfs(int depth){
//깊이가 3으로 배열이 하나 완성됐다면 계산을 해줘야 한다.
if(depth == 3){
//우선순위를 map을 이용해 할당한다.
int value = 3;
map = new HashMap<>();
for(char tmp : make){
map.put(Character.toString(tmp), value);
value--;
}
//계산한 값과 기존 answer 중 큰 값을 answer에 넣는다.
long tmp_c = cal();
if(answer < tmp_c){
answer = tmp_c;
}
return;
}
//우선순위 배열 만들기
for(int i=0; i<3; i++){
if(!visit[i]){
visit[i] = true;
make[depth] = arr[i];
dfs(depth+1);
visit[i] = false;
}
}
}우선순위 map이 다 만들어졌다면 해당 map을 가지고 계산을 해줘야 한다.
먼저 우선순위를 가지고 후위 수식을 만들어줄 리스트를 하나 선언한다.
기존 리스트를 돌면서 숫자가 나오면 후위 수식 리스트에 그냥 넣어주고 연산자가 나오면 스텍에 값이 존재하며 제일 꼭대기 값이 해당 연산자보다 우선순위가 높거나 같을 경우 pop해서 후위 수식 리스트에 넣어준다. 그렇지 않아면 해당 연산자를 스텍에 넣어준다.
while문을 돌리며 스텍에 있는 나머지 값도 잊지 않고 후위 수식 리스트에 넣어야 한다.
//우선순위대로 후위 연산자를 만들어 준다.
for(String tmp : list){
if("*".equals(tmp) || "+".equals(tmp) || "-".equals(tmp)){
while(!stack.isEmpty() && (map.get(stack.peek()) >= map.get(tmp))){
post.add(stack.pop());
}
stack.push(tmp);
}else{
post.add(tmp);
}
}
while(!stack.isEmpty()){
post.add(stack.pop());
} 후위 수식을 전부 만들었다면 이제는 계산을 해야 한다.
후위 수식 리스트를 돌리면서 숫자가 나오면 그냥 계산 스텍에 넣어주고 연산자가 나오면 스텍에서 값 두 개를 빼서 해당 연산을 해주면 된다. 여기서 조심할 점은 빼기의 경우 순서가 중요하므로 스텍인 후입선출 같은 자료형의 경우 두 번째로 뺀 값을 첫 번째로 뺀 값으로 빼줘야 한다.
//만들어진 후위수식을 이용해 값을 계산한다.
for(String tmp : post){
if("*".equals(tmp) || "+".equals(tmp) || "-".equals(tmp)){
Long first = c.pop();
Long second = c.pop();
String op = tmp;
switch(op){
case "*":
c.push(first * second);
break;
case "+":
c.push(first + second);
break;
case "-":
c.push(second - first);
break;
}
}else{
c.push(Long.parseLong(tmp));
}
}계산을 전부 했다면 계산한 값을 가지고 answer과 비교해서 더 큰 값을 answer에 넣어주면 된다.
코드
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Stack;
class Solution {
public static List<String> list;
public static char[] arr;
public static boolean[] visit;
public static char[] make;
public static Map<String, Integer> map;
public static long answer;
public long solution(String expression) {
answer = 0;
list = new ArrayList<String>();
String num = "";
//연산자와 숫자를 따로 리스트에 넣어준다.
for(int i=0; i<expression.length(); i++){
if(expression.charAt(i) == '+' || expression.charAt(i) == '-' || expression.charAt(i) == '*'){
list.add(num);
list.add(Character.toString(expression.charAt(i)));
num = "";
}else{
num += expression.charAt(i);
}
}
list.add(num);
//우선순위 구하기 위한 배열 초기값
arr = new char[] {'+', '-', '*'};
visit = new boolean[3];
make = new char[3];
//우선순위 구하기
dfs(0);
return answer;
}
//연산자 우선순위 만들기
public static void dfs(int depth){
//깊이가 3으로 배열이 하나 완성됐다면 계산을 해줘야 한다.
if(depth == 3){
//우선순위를 map을 이용해 할당한다.
int value = 3;
map = new HashMap<>();
for(char tmp : make){
map.put(Character.toString(tmp), value);
value--;
}
//계산한 값과 기존 answer 중 큰 값을 answer에 넣는다.
long tmp_c = cal();
if(answer < tmp_c){
answer = tmp_c;
}
return;
}
//우선순위 배열 만들기
for(int i=0; i<3; i++){
if(!visit[i]){
visit[i] = true;
make[depth] = arr[i];
dfs(depth+1);
visit[i] = false;
}
}
}
//만들어진 우선순위대로 계산하기
public static long cal(){
Stack<String> stack = new Stack<String>();
List<String> post = new ArrayList<String>();
Stack<Long> c = new Stack<Long>();
long result = 0;
long n = 0;
//우선순위대로 후위 연산자를 만들어 준다.
for(String tmp : list){
if("*".equals(tmp) || "+".equals(tmp) || "-".equals(tmp)){
while(!stack.isEmpty() && (map.get(stack.peek()) >= map.get(tmp))){
post.add(stack.pop());
}
stack.push(tmp);
}else{
post.add(tmp);
}
}
while(!stack.isEmpty()){
post.add(stack.pop());
}
//만들어진 후위수식을 이용해 값을 계산한다.
for(String tmp : post){
if("*".equals(tmp) || "+".equals(tmp) || "-".equals(tmp)){
Long first = c.pop();
Long second = c.pop();
String op = tmp;
switch(op){
case "*":
c.push(first * second);
break;
case "+":
c.push(first + second);
break;
case "-":
c.push(second - first);
break;
}
}else{
c.push(Long.parseLong(tmp));
}
}
result = Math.abs(c.peek());
return result;
}
}