Cooper's devlog

[문제를 접근방법]

이 문제는 컨셉을 어떻게 잡느냐에 따라서 문제를 푸는 시간이 좌지우지되는 문제입니다. 

여기서 문제의 핵심은 '괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.'

여기서 적절히라는 의미는 괄호를 여러개 쳐도 상관없다는 것을 의미합니다.

이 것을 식을 통해서 확인해보겠습니다.

30 +40 -45 +60 + 75 - 80 + 20

이 경우를 확인해보면 괄호를 어떻게 쳐야 할까요?

30 + 40 -(45 + 60 + 75) - (80 + 20)

이렇게 괄호를 친다면 가장 작은 최소값을 얻을 수 있을 겁니다.

그렇다면 두 식을 한번 비교해보겠습니다.

-30 + 40 + 56 + 60 + 70

-30 + 40 - 56 - 60 + 70

이 두 수의 최소값을 어떻게 될까요?

- (30 + 40 +56 + 60 + 70)

-(30 + 40) -(56 + 60 + 70)

이런 형식의 괄호를 칠 수 있습니다. 

결국 최소값은 둘다 같은 값(-256)이 됩니다.

그렇다면 규칙은 어떻게 되는걸까요?

규칙성은 바로 (-)가 시작되는 지점을 기준으로 오른쪽 부분을 모두 뺴는 것입니다.

이유는 괄호를 여러개칠 수 있는 상황에서 (-) 가 여러개 있어도 결국에는 첫 (-)가 존재하는 위치의 결과와 같습니다.

규칙성을 찾았다면 아래 코드를 보면서 확인해보겠습니다.

[문제 해결 코드1]

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String expression = scanner.nextLine();
        int[] numbers = seperateNumber(expression);
        String[] formulas = seperateFormula(expression);

        System.out.println(greedy(numbers, formulas));

        scanner.close();
    }

    private static String[] seperateFormula(String expression) {
        List<String> formulaList = new ArrayList<>();

        for (int index = 0; index < expression.length() - 1; index++) {
            String temp = expression.substring(index, index+1);
            if(temp.equals("+") || temp.equals("-")) {
                formulaList.add(temp);
            }
        }

        String[] formulas = new String[formulaList.size()];
        return formulaList.toArray(formulas);
    }

    private static int[] seperateNumber(String exprresion) {
        String[] numbersAsStr = exprresion.split("[+-]");
        return Arrays.stream(numbersAsStr).mapToInt(Integer::parseInt).toArray();
    }

    private static int greedy(int[] numbers, String[] formulas) {
        boolean hasMinus = false;
        int sum = numbers[0];
        int formula_index = 0;

        for (int index = 1; index < numbers.length; index++) {
            if(formulas[formula_index++].equals("-")) {
                hasMinus = true;
            }
            sum = hasMinus ? sum - numbers[index] : sum + numbers[index];
        }

        return sum;
    }
}

이 코드의 로직은 다음과 같습니다.

1. 숫자에 해당하는 배열을 선언하고 숫자만 저장하도록 한다.
2. 연산자에 해당하는 배열을 선언하고 연산자에 관해서만 저장하도록 한다.
3. 연산자를 순회하며 숫자들을 더한다.
   1. (-) 부호를 만나게 된다면 hasMinus = true를 선언하고 hasMinus = true일 경우 기존 합과 모든 수들을 뺼셈 연산을 한다.
   2. (-) 부호를 만나지 않는다면, 계속해서 수들을 더한다.

하지만 이 로직은 전체 문자열 순회를 3번을 하게 됩니다 

1. seperateFormula
2. eperateNumber
3. greedy

위와 같이 중복되는 순회를 2번을 더하게 됩니다. 그래서 조금 더 욕심내서 1번만 순회해 레이턴시를 줄이는 코드를 작성해보도록 하겠습니다.

[문제 해결 코드2 : 레이턴시 줄인 코드]

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String expression = scanner.nextLine();
        System.out.println(greedy(expression));

        scanner.close();
    }

    private static int greedy(String expression) {
        char[] charArr = expression.toCharArray();
        boolean hasMinus = charArr[0] == '-' ? true : false;
        int sum = 0;
        String temp = "";

        int index = hasMinus ? 1 : 0;
        while (index < charArr.length) {

            if (charArr[index] == '+' || charArr[index] == '-') {
                sum = hasMinus ? sum - toInt(temp) : sum + toInt(temp);
                temp = "";

                if(charArr[index] == '-') {
                    hasMinus = true;
                }
            } else {
                temp += charArr[index];
            }

            index++;
        }

        return hasMinus ? sum - toInt(temp) : sum + toInt(temp);
    }

    public static int toInt(String str) {
        return Integer.parseInt(str);
    }
}

 위 코드는 이전의 코드에서 메서드 분리한 3가지 내용을 한번에 합쳐놓은 방법입니다.

1. 우선적으로 가장 앞에 (-)를 체크합니다.
2. 없을 경우 숫자를 탐색하고 만약에 연산자를 만날 경우,
3. hasMinus의 여부에 따라서 연산을 다르게 합니다.
   1. hasMinus = false( -연산자를 찾지 못했다 : 더하기하라.)
   2. hasMinus = true ( -연산자를 찾았다 : 모든 수를 뺄셈연산하라)

위와 같은 코드를 작성하게 된다면 중복 순회를 하지 않고 1번만 순회하기 떄문에 기존의 레이턴시를 줄일 수 있습니다.

두 코드를 비교해보면 메모리, 시간차이 모두 잡은 것을 확인할 수 있습니다.

이유는 연산자, 숫자를 담는 추가적인 배열을 선언할 필요가 없고, 순회를 1번만 하기 때문에 두 조건 모두를 개선할 수 있는 코드를 작성할 수 있습니다.

이와 같이 같은 문제를 레이턴시 혹은 메모리를 효율적으로 작성하는 코드를 작성하는 법 또한 알고리즘을 공부하시는데 도움이 될 것이라고 생각합니다!