백트래킹을 통한 next_permutation 구현

프로그래머스 2020 카카오 인턴십 Level 2 문제인 수식 최대화를 Java로 풀어보았다. 이전에 풀었을 때는 c++을 이용해 next_permutation의 존재를 처음 배우고 풀었던 기억이 있는데, Java에는 이 next_permutation을 제공하지 않기 때문에 직접 구현해서 풀어야 했다. 백트래킹을 통해 구현할 수 있는데 이걸 해결하고 나서 본 문제를 풀기 위한 로직을 제대로 짜지 못해 결국 틀렸다. ㅎㅎ 머릿속으로는 어떻게 풀어야할지 그림이 그려지지만 코드로 잘 옮기는 것은 또 다른 문제다.

문제 링크만 올려두겠다.
https://programmers.co.kr/learn/courses/30/lessons/67257

---

연산자 간의 우선순위에 따른 순열 만들기

+,-,* 세 개의 연산자의 우선 순위는 6가지가 나온다. 이 6가지에 대해 모든 결과를 계산해보고 그 중 절댓값이 가장 큰 녀석을 선택해서 반환해야 한다. 주어진 수식에 만약 연산자가 두 개만 쓰였더라도 상관없다. 3개의 연산자를 기본으로 해서 다 계산을 해도 없는 연산자면 그냥 넘어갈 것이기 때문에 3개로 가정하고 풀어도 상관없다.

3개의 연산자를 대상으로 6가지 조합을 모두 이용하는 것은 백트래킹을 통해 구현이 가능하다. 다음은 연산자 조합만 만들어내는 코드 일부다.

static char[] priority = { '+', '-', '*' };
static boolean[] checked = new boolean[3];
    
static void backTracking(int cnt, char[] op){
        if(cnt==3){
            ... // 이 부분은 수식 계산 부분
        }
        for(int i=0; i<3; i++){ // 가능한 모든 우선순위 조합을 만들자
            if(!checked[i]){
                checked[i] = true;
                op[cnt] = priority[i];
                backTracking(cnt+1, op);
                checked[i] = false;
            }
        }
    }

백트래킹을 이용해 next_permutation을 구현하는 것은 다음 페이지를 참고했다.
https://velog.io/@junhok82/Java%EB%A1%9C-%EC%88%9C%EC%97%B4Permutation-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

---

실제 계산 과정

처음 수식을 입력 받고나서 operands List와 operators List로 분리를 해준다. 피연산자와 연산자 List로 분리하는 것이다.
그리고 6가지 가능한 연산자 우선순위 조합마다 이 둘을 임시로 복사해서 tmpOperators List 에서 우선순위 연산자를 앞에서부터 탐색하며 해당 연산자를 만나면 중간 두 피연산자와 연산자를 param으로 넘겨줘서 계산 결과를 tmpOperands List에 추가해주는 것이다. 물론, 기존의 두 피연산자와 연산자는 remove(index) 메소드를 통해 제거해준다.

바로 이 제거 부분이 조금 머리를 굴려야 Index Error 를 받지 않고 잘 계산할 수 있다.
아래가 이 계산 과정 코드다.

LinkedList<Long> tmpOperands = new LinkedList<>();   LinkedList<Character> tmpOperators = new LinkedList<>();
tmpOperands.addAll(operands);   tmpOperators.addAll(operators);

for(int i=0; i<3; i++){
       for(int j=0; j<tmpOperators.size(); j++){ // 정적인 size 값으로 계산하는 게 아니라, 중간에 삭제가 일어나니까 동적인 size로 범위를 설정해야 한다. 
               if(op[i]==tmpOperators.get(j)){
                    long tmp = calculator(tmpOperands.remove(j), tmpOperands.remove(j), op[i]);
                    tmpOperands.add(j, tmp);
                    tmpOperators.remove(j);
                    j--; // 이 부분이 중요하다. 두 개 제거했으니 한 칸 뒤로 땡겨야 정상적인 순서로 계산을 이어갈 수 있다.
                }
            }
        }
        result = (result<Math.abs(tmpOperands.peek()) ? Math.abs(tmpOperands.peek()) : result);
    }

연산자 List가 계산 과정 중간에 계속 삭제가 일어나니까 동적인 size로 for문의 조건을 설정해주는 것이 중요하다.
또한 삭제가 발생하면 index 를 한 칸 뒤로 땡겨주는 작업도 반드시 필요하다. 그렇지 않으면 그냥 건너 뛰어버리는 부분이 생긴다.

---

나머지 부분은 그냥 간단한 작업들을 따로 분리해준 메소드 코드만 조금 추가될 뿐이다.
아래는 내가 제출한 전체 코드다.

import java.io.*;
import java.util.*;

public class Maximize {
    static long result = Long.MIN_VALUE;
    static char[] priority = { '+', '-', '*' };
    static boolean[] checked = new boolean[3];
    static LinkedList<Long> operands = new LinkedList<>();
    static LinkedList<Character> operators = new LinkedList<>();

    static long solution(String expression) {
        divideOperatorsOperands(expression);
        backTracking(0, new char[3]);
        return result;
    }

    public static void main(String args[]) throws IOException {
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        String expression = "50*6-3*2";
        bfw.write(String.valueOf(solution(expression)));
        bfw.close();
    }

    static void backTracking(int cnt, char[] op){
        if(cnt==3){
            LinkedList<Long> tmpOperands = new LinkedList<>();   LinkedList<Character> tmpOperators = new LinkedList<>();
            tmpOperands.addAll(operands);   tmpOperators.addAll(operators);

            for(int i=0; i<3; i++){
                for(int j=0; j<tmpOperators.size(); j++){
                    if(op[i]==tmpOperators.get(j)){
                        long tmp = calculator(tmpOperands.remove(j), tmpOperands.remove(j), op[i]);
                        tmpOperands.add(j, tmp);
                        tmpOperators.remove(j);
                        j--;
                    }
                }
            }
            result = (result<Math.abs(tmpOperands.peek()) ? Math.abs(tmpOperands.peek()) : result);
            return;
        }
        for(int i=0; i<3; i++){ // 가능한 모든 우선순위 조합을 만들자
            if(!checked[i]){
                checked[i] = true;
                op[cnt] = priority[i];
                backTracking(cnt+1, op);
                checked[i] = false;
            }
        }
    }

    static Long calculator(Long a, Long b, char operator){
        long result = 0;
        switch(operator){
            case '+':
                result = a + b;
                break;
            case '-':
                result = a - b;
                break;
            case '*':
                result = a * b;
                break;
        }
        return result;
    }

    static void divideOperatorsOperands(String expression){
        String tmpOperands = "";
        for(int i=0; i<expression.length(); i++){
            char cur = expression.charAt(i);
            if(cur=='+' || cur=='-' || cur=='*') {
                operands.add(Long.parseLong(tmpOperands));
                tmpOperands = "";
                operators.add(cur);
            }
            else{
                tmpOperands += cur;
            }
        }
        operands.add(Long.parseLong(tmpOperands));
    }
}

이번에도... 내 힘으로 풀지 못했다. 기분이 더럽따!! 나으 부족함을 인정하고... 더 노오오오오력하자!!

오늘 배운 것

1. Java 에서는 next_permutation을 제공하지 않는다. 백트래킹을 이용해 직접 구현할 수 있다.
2. 중간에 삭제가 일어나는 List를 쭉 순회하며 탐색할 때는 반드시 적절한 index 조절이 필요하다.
3. 카카오 코테는 존나 어렵다.