프로그래머스(수식 최대화)-스택,후위 표기식

https://school.programmers.co.kr/learn/courses/30/lessons/67257

프로그래머스

1. 걸린 시간

모른다. 중간에 초기화돼서

한 1시간쯤 걸린듯 싶다.

 

2. 트리거

우선, 각 + - * 의 우선 순위 별 절댓값의 최댓값을 구하는 문제이다.

우선순위 별 연산을 할 때, 스택을 이용한 후위 표기식으로 풀 수 있다.

즉,

1. 조합을 구한다.(나는 구현으로 해줬다.)

2. 후위 표기식을 구한다.

3. 계산해준다.

4. for문으로 조합 별 2~3을 반복하낟.

이렇게 풀면된다.

 

카카오는 문자열을 참 좋아하는 것 같다.

import java.util.*;

class Solution {
    List<String> list;
    Map<Character, Integer> priority = new HashMap<>();
    public long solution(String expression) {
        initialize(expression);
        return solve();
    }
    
    private long solve() {
        long max = 0;
        for(int i = 1; i <= 6; i++) {
            makePriority(i);
            List<String> postfix = getPostfix();
            max = Math.max(max, Math.abs(getMax(postfix)));
        }
        return max;
    }
    
    private long getMax(List<String> postfix) {
        Stack<Long> stack = new Stack<>();
        for(String curr : postfix) {
            if(isNum(curr)) {
                stack.push(Long.parseLong(curr));
                continue;
            }
            
            long second = stack.pop();
            long first = stack.pop();
            if(curr.equals("*")) {
                stack.push(first * second);
                continue;
            }
            if(curr.equals("-")) {
                stack.push(first - second);
                continue;
            }
            if(curr.equals("+")) {
                stack.push(first + second);
                continue;
            }
        }
        return stack.pop();
    }
    
    private List<String> getPostfix() {
        List<String> postfix = new ArrayList<>();
        Stack<String> stack = new Stack<>();

        for (String str : list) {
            if (isNum(str)) {
                postfix.add(str);
                continue;
            }

            char curr = str.charAt(0);
            while (!stack.isEmpty()) {
                char top = stack.peek().charAt(0);
                if (priority.get(curr) > priority.get(top)) break;
                postfix.add(stack.pop());
            }
            stack.push(str);
        }

        while (!stack.isEmpty()) postfix.add(stack.pop());
        return postfix;
    }
    
    private void makePriority(int i) {
        switch(i) {
            case 1: {
                priority.put('*', 3);
                priority.put('+', 2);
                priority.put('-', 1);
                break;
            }
            case 2: {
                priority.put('*', 3);
                priority.put('+', 1);
                priority.put('-', 2);
                break;
            }
            case 3: {
                priority.put('*', 2);
                priority.put('+', 3);
                priority.put('-', 1);
                break;
            }
            case 4: {
                priority.put('*', 1);
                priority.put('+', 3);
                priority.put('-', 2);
                break;
            }
            case 5: {
                priority.put('*', 1);
                priority.put('+', 2);
                priority.put('-', 3);
                break;
            }
            case 6: {
                priority.put('*', 2);
                priority.put('+', 1);
                priority.put('-', 3);
                break;
            }
        } 
    }
    
    private boolean isNum(String str) {
        try {
            Integer.parseInt(str);
            return true;
        } catch (Exception e) {
            return false;
        }
    }
    
    private void initialize(String expression) {
        list = new ArrayList<>();
        
        String num = "";
        for(int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            if(Character.isDigit(ch)) {
                num += ch;
                continue;
            }
            list.add(num);
            num = "";
            list.add(String.valueOf(ch));
        }
        list.add(num);
    }
}