[pgm_67257] 수식 최대화 (java)

문제링크

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

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 Deque

+ 와 - 그리고 * 세개의 연산자의 우선순위를 서로 다르게 하여 계산한 결과의 절대값이 최대가 되는 값을 찾는 문제이다.

연산자 3개에 대한 서로 다른 우선순위가 있는 경우의 수는 6가지 밖에 없으므로 모든 경우를 계산해주고 최대값을 구해주었다.

 

이때 자료구조는 Deque를 사용해주었다.Deque는 Queue + stack의 자료구조이다. 앞과 뒤로 add를 할 수 있으며, stack처럼 가장 최근에 삽입한 데이터를 뺄 수 도있고, queue처럼 가장 처음에 넣은 데이터를 뺄 수도 있다. 만약 연산을 해줘야하는 상황이면 연산된 결과를 다시 사용해야하는데 이 때는 queue의 앞부분에 넣어주어 바로 연산을 할 수 있도록 해줄 수 있으므로 Deque가 적당하다고 생각되어 사용하였다.

 

연산자 3개에 대한 경우의 수를 미리 배열로 정해둔 뒤 연산자의 우선순위를 변경해가며 정답을 구해주었다. 항상 올바른 데이터가 들어오기 때문에 연산을 해주기 전에 3개를 queue에서 꺼내고, 만약 연산을 하게 되면 맨 앞으로 넣어주고 연산을 못하게 되면 끝에 있는 숫자 값만 넣어주고 다른 2개는 새로운 queue에 넣어주어 다음 연산자를 연산할 때 계산되도록 구현해주었다.

 

구현코드

package pgm_67257;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class Solution {

    public long solution(String expression) {
        char[] operations = {'+', '-', '*'};
        Deque<String> queue = new LinkedList<>();

        String number = "";
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (isOperation(c)) {
                queue.add(number);
                number = "";
                queue.add(String.valueOf(c));
                continue;
            }
            number = number + c;
        }
        queue.add(number);

        long max = 0;
        int[][] priors = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};
        for (int i = 0; i < priors.length; i++) {
            Deque<String> calQueue = queueCopy(queue);

            for (int j = 0; j < priors[i].length; j++) {
                Deque<String> newQueue = new LinkedList<>();
                while (!calQueue.isEmpty()){
                    if(calQueue.size() == 1 && newQueue.isEmpty())
                        break;
                    else if(calQueue.size() == 1){
                        newQueue.add(calQueue.remove());
                        break;
                    }


                    String front = calQueue.remove();
                    String operation = calQueue.remove();
                    String back = calQueue.remove();

                    if (operations[priors[i][j]] == operation.charAt(0)) {
                        calQueue.addFirst(calculation(Long.valueOf(front), Long.valueOf(back), operation.charAt(0)));
                    } else {
                        newQueue.add(front);
                        newQueue.add(operation);
                        if(calQueue.isEmpty())
                            newQueue.add(back);
                        else
                            calQueue.addFirst(back);
                    }
                }
                if(calQueue.size() != 1)
                    calQueue = newQueue;
            }
            long val = Math.abs(Long.valueOf(calQueue.remove()));
            max = max < val ? val : max;
        }
        return max;
    }

    public Deque<String> queueCopy(Deque<String> queue){
        ArrayList<String> list = new ArrayList<>();
        while (!queue.isEmpty()){
            list.add(queue.remove());
        }

        Deque<String> resultQueue = new LinkedList<>();
        for(int i = 0; i < list.size(); i++){
            resultQueue.add(list.get(i));
            queue.add(list.get(i));
        }
        return resultQueue;
    }

    public String calculation(long a, long b, char operation) {
        if (operation == '+')
            return String.valueOf(a + b);
        else if (operation == '-')
            return String.valueOf(a - b);
        else
            return String.valueOf(a * b);
    }

    public boolean isOperation(char c) {
        return c == '+' || c == '*' || c == '-';
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)