프로그래머스 - 수식 최대화

수식 최대화 : https://programmers.co.kr/learn/courses/30/lessons/67257

Problems

---

Solves

String타입인 expression을 숫자와 연산자를 분리하고 해당 숫자에 연산자를 붙여서 연산자의 우선순위를 모두 탐색하며 최대값을 찾는 완전탐색으로 생각했다.

먼저 expression에서 숫자를 linkedList에 모두 저장한다. 그리고 연산자는 따로 list에 저장해 두었다가 연산자는 숫자의 총 갯수보다 1개가 적기 때문에 linkedList의 index를 통해 해당 숫자에 연산자를 갱신해 준다.

그렇게 되면 위의 expression Num처럼 linkedList에 저장이 된다.

그리고 나서 따로 중복을 제거한 연산자 리스트를 통해 백트래킹을 하여 모든 연산자의 우선순위를 탐색하며 linkedList를 깊은 복제하여 아래 사진과 같이 앞의 숫자와 연산하여 앞 숫자에 결과값을 저장하고 해당 숫자는 삭제(LinkedList로 구현한 이유)해주는 방식으로 반복하다보면 모든 연산자에 대한 연산이 끝났을때 linkedList의 첫번째에만 값이 저장되어있다.

linkedList의 첫번째 값을 최대값으로 갱신하고나면 모든 연산자를 완탐했을때의 최대 값을 반환하면 된다.

---

Code

import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
class Solution {
	//주어진 피연산자를 저장
    LinkedList<Number> numberLinkedList;
    //중복을 제거한 연산자 저장
    List<Character> operation;
    //백트래킹때 사용
    boolean[] check;
    long res;
    public long solution(String expression) {
        numberLinkedList = new LinkedList<>();
        operation = new ArrayList<>();
        
        //numberLinkedList의 숫자에 연산자를 갱신하기 위한 리스트
        List<Character> opList = new ArrayList<>();
        char[] expressionArr = expression.toCharArray();
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<expressionArr.length;i++){
            char c = expressionArr[i];
            if(c >= '0' && c <= '9'){
                sb.append(c);
            }else{
            	//연산자일 경우
                if(!operation.contains(c)){
                	//중복을 제거한 연산자 저장
                    operation.add(c);
                }
                //피연산자 저장, 연산자는 '+'로 일단 초기화
                numberLinkedList.add(new Number(Integer.parseInt(sb.toString()),'+'));
                //numberLinkedList의 숫자에 연산자를 저장하기 위해 저장
                opList.add(c);
                sb = new StringBuilder();
            }
        }
        //마지막 피연산자 저장
        numberLinkedList.add(new Number(Integer.parseInt(sb.toString()),'+'));
        for(int i=1;i<numberLinkedList.size();i++){
            numberLinkedList.get(i).op = opList.get(i-1);
        }
        
        check = new boolean[operation.size()];
        res = Long.MIN_VALUE;
        operate(0, numberLinkedList);
        
        return res;
    }
    
    //완탐 & 백트래킹
    void operate(int count, LinkedList<Number> ll){
    	//주어진 연산자에 대해 우선순위를 매겼을때
        if(count >= operation.size()){
        	//linkedList의 첫번째 값을 최대값으로 갱신
            res = Math.max(res, Math.abs(ll.get(0).num));
            return;
        }
        
        for(int i=0;i<operation.size();i++){
            if(!check[i]){
            	//expression길이가 최대 100인데 피연산자의 갯수는 약 50개 정도이니 깊은 복사가 가능
                LinkedList<Number> copyNumberLinkedList = copyNumberLinkedList(ll);
                int idx = 1;
                //copyNumberLinkedList에서 삭제가 발생하기 때문에 index 별도로 관리
                while(idx<copyNumberLinkedList.size()){
                    Number currentNumber = copyNumberLinkedList.get(idx);
                    Number prevNumber = copyNumberLinkedList.get(idx-1);
                    
                    //연산을 수행하면 앞의 피연산자의 num에 결괏값을 갱신하고 currentNumber는 삭제
                    if(currentNumber.op == operation.get(i)){
                        switch(currentNumber.op){
                            case '+':
                                copyNumberLinkedList.get(idx-1).num = prevNumber.num + currentNumber.num;
                                copyNumberLinkedList.remove(currentNumber);
                                break;
                            case '-':
                                copyNumberLinkedList.get(idx-1).num = prevNumber.num - currentNumber.num;
                                copyNumberLinkedList.remove(currentNumber);
                                break;
                            case '*':
                                copyNumberLinkedList.get(idx-1).num = prevNumber.num * currentNumber.num;
                                copyNumberLinkedList.remove(currentNumber);
                                break;
                        }
                    }else{
                    	//연산을 수행하지 않으면 index 이동
                        idx++;
                    }
                }
                
                //백트래킹
                check[i] = true;
                operate(count+1, copyNumberLinkedList);
                check[i] = false;
            }
        }
    }
    
    //linkedList 깊은 복사
    LinkedList<Number> copyNumberLinkedList(LinkedList<Number> ll){
        LinkedList<Number> copyll = new LinkedList<>();
        for(Number n : ll){
            copyll.add(new Number(n.num,n.op));
        }
        return copyll;
    }
    
    static class Number{
        long num;
        char op;
        public Number(long num, char op){
            this.num = num;
            this.op = op;
        }
    }
}

---

Result