[알고리즘] 백준 1541 - 잃어버린 괄호

문제 본문

그리디 알고리즘, 탐욕법이라고 불리는 이 알고리즘은 원하는 답을 구하기 위해 모든 경우를 탐색하는 것이 아니라 문제를 해결하는 과정에서 최적이라고 생각하는 과정을 선택하는 알고리즘입니다.

 

문제 해석

Input: 55-50+40   output: -35

문제를 설명하자면 괄호가 생략된 수식에서 괄호를 집어넣어 최솟값을 만들어라!입니다. 예시로 주어진 입력으로 만들어 낼 수 있는 최솟값의 수식은 55-(50+40)입니다.

여기서 우리가 문제를 풀기위해 적용해야 하는 그리디 알고리즘 괄호를 수식에서 숫자를 제외한 모든 곳에 넣어서 결과를 계산한 후 최소 값을 찾는 것이 아니라 답을 구하기 위한 문제의 최적 방법을 찾는 것이죠. 최소 값을 구하기 위한 최적 방법은 최대한 크게 빼는 것입니다.

 

Input: 10-10+10-10+10   output: -30

'+','-',와 9 이하의 양수로 구성된 식에서 적절하게 괄호를 집어넣어 최대한 크게 빼기 위해서는 뺄셈 하는 오른쪽 피연 사자의 절댓값을 크게 만들어 주면 됩니다. 주어진 예시에 최적 방법에 맞게 괄호를 집어넣은 수식은 10-(10+10)-(10+10)입니다.

위의 방법을 코딩으로 구현해보도록 하겠습니다. 일단 +,-,숫자를 구분하기 위해 char 자료형으로 하나씩 비교해야 합니다.

들어오는 char 값이 숫자일 경우

StringBuilder stringToNumberTemp = new StringBuilder();
 if (c >= '0' && c <= '9') { 
    stringToNumberTemp.append(numberOrWord);
 } ...

char 자료형의 숫자 범위는 위와 같은 조건식으로 구할 수 있습니다. 숫자일 경우 StringBuilder에 저장하는 이유는 입력에서 주어지는 피연산자의 길이가 최대 5이기 때문입니다. 숫자의 길이가 1이라면 들어오는 입력이 고대로 숫자로 표현될 수 있지만 길이가 5라면 십의 자리 수인지 백의 자리 수인지 알 수 없기 때문이죠. 또 문제의 조건에서 숫자는 0으로 시작할 수 있다는 조건이 있어 String으로 모두 저장한 후 Int로 변환해준다면 0으로 시작하는 숫자도 알맞게 변환될 수 있습니다.

 

들어오는 char 값이 +,-일 경우

 

int answer = 0; //이 변수의 값이 답
int numberTemp = 0;   
 // +, - 모두 해당
numberTemp += Integer.parseInt(stringToNumberTemp.toString());
stringToNumberTemp = new StringBuilder();

들어오는 값이 +,- 일 경우 StringBuilder에 저장된 String은 하나의 피연 사자라고 봐야 합니다. 그래서 저장되어 있는 값을 Integer class 함수를 이용해 숫자로 변경해줍니다. 이후 새로운 피연 사자를 받아들이기 위해 StringBuilder 값을 초기화합니다.

 

그중 들어오는 값이 - 일 경우

최적의 방법은 빼는 피연산자의 절댓값을 크게 만드는 것입니다. 위 코드에서 numberTemp 변수가 그 역할을 수행합니다. -가 아닌 + 기호를 만날 때마다 만들어진 피연산자의 값을 하나하나 더하여 저장해 놓고 - 기호를 만날 때 저장된 숫자 값을 answer에서 빼는 것입니다. 다만 55-50+40 수식에서 처럼 - 기호가 나오기 이전 피연산자들은 answer에 양수로 저장되어야 하므로 그것을 구별한 boolean 값을 추가합니다.

 

전체 코드

import java.util.Scanner;

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

        int answer = 0;
        StringBuilder stringToNumberTemp = new StringBuilder();
        int number = 0;
        boolean isMinus = false;

        for (int index = 0; index < numbers.length(); index++) {

            char numberOrWord = numbers.charAt(index);

            if (numberOrWord >= '0' && numberOrWord <= '9') { //숫자일 경우
                stringToNumberTemp.append(numberOrWord);
            } else {
                number += Integer.parseInt(stringToNumberTemp.toString());
                stringToNumberTemp = new StringBuilder();

                if (numberOrWord == '-') {
                    if (isMinus) {
                        number *= -1;
                    } else {
                        isMinus = true;
                    }
                    answer += number;
                    number = 0;
                }
            }
        }
        //수식은 마지막에 숫자로 끊이 난다. 따라서 마지막에 저장되어 있던 숫자를 계산해준다.
        number += Integer.parseInt(stringToNumberTemp.toString());
        if (isMinus) number *= -1;

        answer += number;

        System.out.println(answer);
    }
}