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

🖇️ 문제 링크

코딩테스트 연습 - 수식 최대화

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다. 해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.

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

 

---

📝 문제 분석

연산자 세 개의 우선 순위 조합을 모두 만들어 봅니다. 우선 순위에 따라 스택 계산기를 구현하여 나온 절댓값의 최댓값을 리턴합니다.

 

---

⌨️ 코드

import java.util.*;

class Solution {
    List<Long> nums = new ArrayList<>();
    List<Character> ops = new ArrayList<>();
    boolean[] chk = new boolean[3];
    int[] pick = new int[3];
    Map<Character, Integer> pri = new HashMap<>();
    long ans = 0;

    public long solution(String expression) {
        String tmp = "";
        for(char c : expression.toCharArray()) {
            if(c == '+' || c == '-' || c == '*') {
                ops.add(c);
                nums.add(Long.parseLong(tmp));
                tmp = "";
            } else
                tmp += c;
        }
        nums.add(Long.parseLong(tmp));

        perm(0);
        return ans;
    }

    public void perm(int cnt) {
        if(cnt == 3) {
            pri.put('+', pick[0]);
            pri.put('-', pick[1]);
            pri.put('*', pick[2]);

            ans = Math.max(ans, getValue());
            return;
        }

        for(int i = 0; i < 3; i++) {
            if(!chk[i]) {
                chk[i] = true;
                pick[cnt] = i;
                perm(cnt + 1);
                chk[i] = false;
            }
        }
    }

    public long getValue() {
        Deque<Long> numStk = new ArrayDeque<>();
        Deque<Character> opStk = new ArrayDeque<>();

        numStk.push(nums.get(0));
        int idx = 0;
        for(char op : ops) {
            while(!opStk.isEmpty() && pri.get(opStk.peek()) >= pri.get(op))
                numStk.push(calc(numStk.pop(), numStk.pop(), opStk.pop()));

            numStk.push(nums.get(++idx));
            opStk.push(op);
        }

        while(!opStk.isEmpty())
            numStk.push(calc(numStk.pop(), numStk.pop(), opStk.pop()));

        return Math.abs(numStk.pop());
    }

    public long calc(long a, long b, char op) {
        if(op == '+') return a + b;
        else if(op == '-') return b - a;
        else return a * b;
    }

}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0