[JAVA/프로그래머스] 2020 카카오 인턴십: 수식 최대화

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
import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
    char[] oper={'+','-','*'};
    boolean[] visit;
    HashMap<Character, Integer> map;
    long answer;
    public long solution(String expression) {
        answer = 0;
        visit=new boolean[3];
        map=new HashMap<>();
        perm(0, expression);
        return answer;
    }
    
    public void perm(int idx, String exp){
        if(idx==3){ // 우선순위 세팅 완료
            ArrayList<String> list=postfix(exp); // 우선순위에 맞춰 후위식 변환
            long ret=calculate(list); // 결과 값
            answer=Math.max(answer, Math.abs(ret));
            return;
        }
        for(int i=0;i<3;i++){
            if(visit[i]) continue; // 이미 사용한 연산자
            visit[i]=true; // i를 idx번째 우선순위로 사용
            map.put(oper[i], idx);
            perm(idx+1, exp); // idx+1번째 우선순위 세팅
            visit[i]=false; // i를 idx번째로 사용하지 않는 경우
        }
    }
    
    public long calculate(ArrayList<String> list){
        Stack<Long> st=new Stack<>(); // 숫자 저장
        for(String s:list){
            if(s.equals("+")){
                long b=st.pop();
                long a=st.pop();
                st.push(a+b);
            }
            else if(s.equals("-")){
                long b=st.pop();
                long a=st.pop();
                st.push(a-b);
            }
            else if(s.equals("*")){
                long b=st.pop();
                long a=st.pop();
                st.push(a*b);
            }
            else st.push(Long.parseLong(s));
        }
        return st.pop(); // stack에 남아있는 마지막 값이 결과값
    }
    
    public ArrayList<String> postfix(String exp){
        ArrayList<String> result=new ArrayList<>(); // 후위식
        StringBuilder num=new StringBuilder(); // 숫자
        Stack<Character> st=new Stack<>(); // 연산자 저장
        
        for(int i=0;i<exp.length();i++){
            char ch=exp.charAt(i);
            if(ch=='+' || ch=='-' || ch=='*'){ // 연산자인 경우
                result.add(num.toString()); // 현재까지의 숫자를 result에 저장
                num.setLength(0); // 다음 숫자 만들기 위해 초기화
                // 후위식 코드
                while(!st.isEmpty() && map.get(st.peek())>=map.get(ch))
                    result.add(st.pop()+"");
                st.push(ch);
            }
            else num.append(ch); // 숫자인 경우
        }
        
        // 아직 result에 저장되지 못한 값들 체크
        if(num.length()>0) result.add(num.toString());        
        while(!st.isEmpty()){
            result.add(st.pop()+"");
        }
        
        return result;
    }
}