[level 2] [카카오 인턴] 수식 최대화 - 67257 (JAVA)

문제 요약

문제는 주어진 수식 문자열에서 연산자의 우선순위를 바꾸어 가능한 모든 조합을 만들고, 그 중에서 각 경우의 절대값이 가장 큰 결과를 반환하는 것이다.

 

---

문제 분석

1. 주어진 수식 문자열을 토큰화하여 연산자와 피연산자를 구분한다.
2. 가능한 모든 연산자 우선순위 조합을 구한다.
3. 각 조합에 대해 주어진 수식을 계산하고, 절대값이 가장 큰 결과를 구한다

---

코드

import java.util.*;

class Solution {
    static long max;
    static String[] std = {"+", "-", "*"};
    
    public long solution(String expression) {
        max = 0;
        // 특정 구분자를 기반으로 문자열 나누기
        StringTokenizer st = new StringTokenizer(expression, "+|-|*", true);
        List<String> tokens = new ArrayList<String>();
        while(st.hasMoreTokens()){
            tokens.add(st.nextToken());
        }
        permutation(tokens, new ArrayList<Integer>(), new boolean[3]);
        return max;
    }
    
    // 연산자 우선순위를 구하고, 각 경우에 대해 계산을 수행하는 함수
    private void permutation(List<String> tokens, List<Integer> stdList, boolean[] visited){
        if(stdList.size() == 3){
            // 수식 계산 하기
            long currResult = calc(tokens, stdList);
            max = Math.max(max, currResult);
            return;
        }
        // 재귀를 통해 연산자 우선순위 구하기
        for(int i = 0; i < 3; i++){
            if(!visited[i]){
                visited[i] = true;
                stdList.add(i);
                permutation(tokens, stdList, visited);
                visited[i] = false;
                stdList.remove(stdList.indexOf(i));
            }
        }
    }
    
    // 주어진 연산자 우선순위에 따라 수식을 계산하는 함수
    private long calc(List<String> tokens, List<Integer> stdList){
        // 원본 tokens를 보존하기 위해 복사본 생성
        List<String> localTokens = new ArrayList<>(tokens);
        
        // 연산자 우선순위에 따라 계산 진행
        for(int op = 0; op < 3; op++){
            String currOp = std[stdList.get(op)];
            for(int n = 0; n < localTokens.size(); n++){
                if(localTokens.get(n).equals(currOp)){
                    long firstNum = Long.parseLong(localTokens.get(n-1));
                    long secondNum = Long.parseLong(localTokens.get(n+1));
                    Long tempResult = switch(currOp){
                            case "+" -> firstNum + secondNum;
                            case "-" -> firstNum - secondNum;
                            case "*" -> firstNum * secondNum;
                            default -> 0L;
                    };
                    localTokens.set(n-1, tempResult+"");
                    localTokens.remove(n);
                    localTokens.remove(n);
                    n--; // 연산자가 삭제되었으므로 인덱스를 하나 줄여준다.
                }
            }
        }
        return Math.abs(Long.parseLong(localTokens.get(0)));
    }
}

---

정리

새로 배운 내용

StringTokenizer에서 구분자 사이에 |를 넣어 여러개의 구분조건을 만들수 있고, true조건으로 구분자 또한 token으로 만들 수 있다.

개선할 점

tokens를 사용할 때 자바의 객체 참조성을 고려하지 않았다. 함수에 객체를 전달할 떄 객체의 참조(주소)가 전달되고, 함수 내에서 객체를 수정하면 원본 객체가 변경된다. 이 점을 고려하여 복사본을 만들어 원본 리스트에 영향을 주지 않도록 해야한다.

더 찾아볼만한 사항

중위표기법을 후위표기법으로 변환하는 stack을 사용해서 문제를 해결할 수 있다.