[프로그래머스(Programmers)] 수식 최대화 (java) /2020 카카오 채용연계형 인턴십

안녕하세요. 오늘은 프로그래머스의 수식 최대화 문제를 풀어보겠습니다. 이 문제는 2020년도 카카오 채용연계형 인턴십에서 출제되었습니다. 문제를 논리적으로 풀어가는 구현력이 적당히 필요하다고 판단되어 추천문제로 선정하였습니다.

---

1) 문제 링크

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

2) 문제 풀이

✔ 수식을 숫자와 연산자로 split

우선, 주어진 수식을 숫자와 연산자로 split하여 List(코드 내 변수명 allExpression)에 저장합니다. for문을 이용해서 주어진 수식을 한 글자씩 확인하고, 만약 연산자라면 set(코드 내 변수명 beforeDfs)에 따로 저장해서 수식에 있는 연산자들의 종류를 확인합니다.

✔ set에 저장된 연산자들 dfs 돌면서 연산자 조합(우선순위 조합) 생성

set에 따로 저장해 둔 연산자 종류를 가지고 dfs를 돌면서 연산자 조합을 생성합니다. 생성한 연산자 조합은 List(코드 내 변수명 operator)에 String으로 따로 저장해줍니다.
만약 연산자 종류가 (*, -, +) 라면 dfs를 돈 결과는 다음과 같습니다.

우선순위 조합 결과
* - +
* + -
- + *
- * +
+ - *
+ * -

✔ 연산자 조합들을 토대로 수식 계산

연산자 조합이 완성되었으면, 수식을 계산할 차례입니다. 저장된 우선순위에 따라 수식을 계산하면 됩니다.
이 때 중요한점은 계산한 숫자들은 모두 list에서 remove하고, 계산한 결과를 list에 새로 add해줘야 한다는 것입니다.
arraylist는 remove할 경우 저장된 원소들의 index가 변경됩니다. 이러한 사항에 주의하며 뒤에서부터 remove해줍니다.
예를들어, 500 - 20 의 연산을 수행하고, 결과인 480을 새로 넣어야 한다고 가정합시다.

[연산 수행 전 list]

0	1	2	3	4	5	6
a	+	500	-	20	*	b

연산 수행 후에는 list(2), list(3), list(4)를 모두 삭제해야 합니다. arraylist는 요소 삭제 시 뒷쪽에 저장된 값들을 앞으로 당겨서 빈 공간이 없게 만들어줍니다. 그래서 list(4) -> list(3) -> list(2) 순으로 삭제해주면 index가 꼬이지 않고 편리합니다.

[연산 수행 직후 list]

0	1	2	3
a	+	*	b

그 후에는 500 - 20의 결과인 480을 list(2)에 저장해줘야 합니다.

[연산결과 저장 후 최종 list]

0	1	2	3	4
a	+	480	*	b

이를 일반 표현식으로 나타내면 다음과 같습니다.

if(list(j)가 '연산자'와 같다면) {
    1. int result = list(j-1)와 list(j+1) 계산한 결과값
    2. list(j+1), list(j), list(j-1) list에서 remove
    3. list(j-1)에 result 값 add
}

3) 추가 테스트케이스: int를 사용하여 발생하는 문제 확인

초기 채점 시 70점으로 답을 완벽히 맞추지 못했었습니다. 질문목록 탭에 있었던 추가 테스트케이스를 이용해서 답을 완벽히 맞출 수 있었습니다.

input : "177-661X999X99-133+221+334+555-166-144-551-166X166-166X166-133X88X55-11X4+55X888X454X12+11-66+444X99"
output : 6083974714

벨로그에서 곱하기('*') 문자를 제대로 인식하지 못해서 부득이하게 'X'로 표기합니다. 가져가서 쓰실 분들은 치환해서 쓰시면 됩니다.!!

출력되어야 하는 output값과 다르게 1789007418로 나왔는데, 확인해보니 함수에서 long이 아닌 int로 결과를 받아 생기는 문제였습니다. 선언한 숫자형을 int가 아닌 long으로 변환하고 나니 정상적으로 output이 6083974714로 출력되었습니다.

4) 전체 코드

import java.util.*;

class Solution {
    public long solution(String e) {
        sb.delete(0, sb.length());
        beforeDfs = new HashSet<>();
        operator = new ArrayList<>();
        
   	//100,-,200,*,300 이런식으로 수식을 하나씩 저장해둔다
        ArrayList<String> allExpression = makeExpression(e); 
        int setNum = beforeDfs.size();
        visited = new boolean[setNum];
        dfs = new String[setNum];

        dfs(setToList(), setNum, 0);
        return makeAnswer(allExpression, operator.size());
    }

    private static StringBuilder sb = new StringBuilder();
    private static Set<String> beforeDfs;   //expressions에 있는 사칙연산 종류들 나열
    private static List<String> operator;   //사칙연산들 dfs 돌고 난 후 저장하는 곳, (*-+),(*+-),(-+*),(-*+).. 이렇게 저장됨
    private static boolean[] visited;
    private static String[] dfs;

    //전체 expression 띄워서 저장하는 과정
    //List에는 100,-,200, ... 이렇게 하나씩 담김
    private static ArrayList<String> makeExpression(String e) {
        ArrayList<String> list = new ArrayList<>();

        for (int i = 0; i < e.length(); i++) {
            char c = e.charAt(i);

            if (c == '-' || c == '+' || c == '*') {
                String str = Character.toString(c);

                list.add(sb.toString());
                list.add(str);
                beforeDfs.add(str);

                sb.delete(0, sb.length());
            } else {
                sb.append(c);
            }
        }

        list.add(sb.toString());
        sb.delete(0, sb.length());

        return list;
    }

    private static List<String> setToList() {
        return new ArrayList<>(beforeDfs);
    }

    private static void dfs(List<String> list, int size, int index) {
        if (size == index) {
            for (String str : dfs) {
                sb.append(str + "");
            }

            operator.add(sb.toString());
            sb.delete(0, sb.length());
            return;
        }

        for (int i = 0; i < size; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs[index] = list.get(i);
                dfs(list, size, index + 1);
                visited[i] = false;
            }
        }
    }

    private static long makeAnswer(ArrayList<String> allExpression, int dfsSize) {
        long answer = Integer.MIN_VALUE;
        long tmp = 0;

        for (int i = 0; i < dfsSize; i++) {
            String[] split = operator.get(i).split("");
            ArrayList<String> removeList = (ArrayList<String>) allExpression.clone();

            for (String optStr : split) {
                for (int j = 0; j < removeList.size(); j++) {
                    String expression = removeList.get(j);

                    if (optStr.equals(expression)) {
                        long a = Long.parseLong(removeList.get(j - 1));
                        long b = Long.parseLong(removeList.get(j + 1));

                        long calculate = calculate(a, b, expression);

                        removeList.remove(j + 1);
                        removeList.remove(j);
                        removeList.remove(j - 1);

                        removeList.add(j - 1, Long.toString(calculate));

                        j -= 1;
                    }
                }
            }
            tmp = Long.parseLong(removeList.get(0));
            answer = Math.max(answer, Math.abs(tmp));
        }

        return answer;
    }

    private static long calculate(long a, long b, String expression) {
        long num = 0;

        switch (expression) {
            case "-":
                num = a - b;
                break;
            case "+":
                num = a + b;
                break;
            case "*":
                num = a * b;
                break;
            default:
                break;
        }

        return num;
    }
}

5) 특이사항(새로 알게 된 사실)

✔ makeAnswer 함수에서 removeList를 allExpression.clone 하여 선언

makeAnswer 내에 있는 removeList를 초기에는 다음과 같이 선언했습니다.

List<String> removeList = allExpression;

그랬더니 removeList에서 값을 삭제하면 allExpression에 있는 값도 함께 삭제되었습니다.
디버깅 결과, removeList와 allExpression의 id(주소값)이 같아 발생하는 문제였습니다. 해당 방식은 주소값 참조를 이용하기 때문에 removeList에서 값 remove 시 allExpression에서도 함께 지워진다는 사실을 알 수 있었습니다.

따라서 다음과 같이 코드를 변경했습니다.

ArrayList<String> removeList = (ArrayList<String>) allExpression.clone();

clone을 이용했더니 removeList에서 값을 지워도 allExpression에서는 값이 지워지지 않았습니다.

주소값 참조를 이용하는 것과 저장된 값만 가지고 오는 방식의 차이를 느낄 수 있었습니다.

✔ ArrayList.remove -> remove 후 자동으로 남은 자리 매꾼다 (배열과 리스트의 차이)

항상 문제를 풀면서 arraylist를 많이 선언하긴 했지만, arraylist에서 remove는 잘 하지 않아서 'remove후에 남은 index들은 어떻게 되는걸까' 하는 생각이 들었습니다. 확인 결과 arraylist에서 remove를 수행하면 남은 자리를 뒷쪽 index가 메꿔준다는 사실을 알 수 있었고, 배열과 리스트의 차이를 다시 한 번 알 수 있었습니다.

6) 느낀점

풀이코드가 엄청 길다. 문제를 이해하기는 쉽지만 코드를 깨끗하게 짜기는 어려운 문제인 것 같다. (내가 짠 코드도 깨끗하지 않아서 맘에 안든다..)

✔ dfs 짜기 어려웠음

오랫만에 dfs를 이용하려니까 좀 어려웠다. 처음에 static으로 선언해둔 StringBuilder를 이용해보려고 했는데 이게 맘처럼 쉽지가 않았다. (-+), (+-), (+-), (*-).. 자꾸 이런식으로 이상하게 결과가 나왔다.

결국 String배열을 새로 추가해서 dfs 코드를 짰다. 뭔가 쓸데없고 비효율적이라는 느낌이 어렴풋이 든다..

7) 마음에 안 드는 점

✔ 변수가 너무 많음

변수가 너무 많다!! 그리고 쓸데없는 변수를 너무 많이 선언한 것 같다.

✔ int에서 long으로 바꾸기가 어려웠음, 좋지 않은 코드라는 뜻?

추가 테스트케이스를 확인하고 int를 long으로 바꿀 때 어떤 변수를 long으로 바꿔야 할지 좀 가늠이 안됐다. 그리고 int에서 long으로 바꿔야 하는 변수들이 좀 많아가지고 바꾸면서 '아.. 한번에 바꾸면 진짜 좋을 것 같은데..' 하는 생각이 자꾸 들었다. 유지보수하기 어렵게 코드를 짜놨다는 생각이 들었다.

선배님께서 항상 변수를 선언할 때 String int 이렇게 쓰지 말고 래퍼클래스를 이용하라고 해주셨는데, 래퍼클래스를 이용하면 이럴때 참 편하지 않을까 싶다.

✔ 추가 테스트케이스를 생각하지 못함

이건 내 고질적인 단점인 것 같다. 추가 테스트케이스를 생각하지 못하고, 코드가 틀린 이유를 가늠하지 못한다. 어떻게 극복할 수 있을지 모르겠다..

---

[참고한 곳]
https://programmers.co.kr/questions/16678