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

문제

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

언어

자바 JAVA

로직

문제의 핵심은 괄호를 이용해서 가장 큰 음수 값을 뽑아내야 합니다. 예를 들어 55 - 10 + 20 + 30이 존재합니다. 괄호를 이용한다면 '-' 문자를 기준으로 뒤의 숫자들을 괄호로 묶을 수 있습니다.

 

55 - 10 + 20 + 30 --> 55 - (10 + 20 +30) 

 

그렇다면 우리는 입력된 문자열을 '-' 기준으로 구분하여 입력받아야 합니다. 

StringTokenizer는 정규식을 사용하지 않고 구분자로 문자열을 나누어 저장할 수 있습니다. 아래 코드는 입력받은 문자열을 '-'를 기준으로 나누고, 구분자를 같이 저장하기 위해 true를 저장하였습니다.

StringTokenizer st = new StringTokenizer(br.readLine(), "-", true);

// 메서드 정보
StringTokenizer(문자열, 구분자, 구분자를 같이 저장할지 여부)

55 - 10 + 20 + 30 은 다음과 같이 저장됩니다.

입력
55-10+20+30

출력
55
-
10+20+30

 

이제 '-'를 기준으로 나누었으니 저장된 토큰을 하나씩 꺼내서 사용해야 합니다. 문제에서 연산자가 마지막으로 입력될 수 없다고 했으니 꺼낸 token이 '-'라는 것은 다음 token으로 반드시 숫자가 와야 한다는 뜻입니다.

꺼낸 token을 '+'를 기준으로 나누어줍니다. tmp는 괄호로 묶인 숫자들을 저장하는 변수입니다. 55 - 10 + 20 + 30의 경우 (10+20+30)이 저장됩니다. 마지막으로 모두 더한 숫자에 -를 붙여 -(10 + 20 + 30)을 만들어주고 총합을 저장하고 있는 sum에서 빼줍니다.

(참고로 split의 경우 +를 구분자로 사용하려면 이스케이프 문자를 사용해야 합니다. 여기를 참고해주세요.)

if (token.equals("-")) {
    String[] split = st.nextToken().split("\\+");
    int tmp = 0;
    for (int i = 0; i < split.length; i++) {
        tmp += Integer.parseInt(split[i]);
    }
    sum -= tmp;
}

그렇다면 '-'이 아닌 경우에는 숫자 또는 '+'와 숫자로 이루어진 문자열이 저장되어 있을 것입니다.

여기서 2가지 경우의 수로 나뉘는데, 

첫번째는 문자열(token) 안에 연산자가 포함된 경우입니다. 예를 들어 10+20+30+40으로 이루어진 문자열은 위에서 확인한 '-' 연산자를 기준으로 나누어지지 않기 때문에 아래 코드에 해당됩니다. 따라서 이때는 '+'를 기준으로 나누어 모든 값을 더해줍니다.

두 번째는 문자열(token) 안에 연산자가 포함되지 않은 경우로서 바로 sum에 더해줍니다.

else {
    // 문자열에 +으로만 이루어진 경우 -> ex) 10+20+30+40
    if (token.contains("+")) {
        String[] split = token.split("\\+");
        for (int i = 0; i < split.length; i++) {
            sum += Integer.parseInt(split[i]);
        }
    }
    // 숫자로만 이루어진 경우
    else {
        sum += Integer.parseInt(token);
    }
}

---

 최종코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // -를 기준으로 문자열을 나눈다. -> ex) 55 - 10 + 20 + 30를 55 - (10 + 20 + 30)으로 묶기 위함.
        StringTokenizer st = new StringTokenizer(br.readLine(), "-", true);

        int sum = 0;
        // 토큰이 존재하는 동안 반복
        while (st.hasMoreTokens()) {
            // 토큰을 가져온다
            String token = st.nextToken();
            // 위에서 '-'를 기준으로 토큰을 나누었기에 '-' 다음 토큰은 숫자로만 이루어진 문자열 or '+'와 숫자를 포함하는 문자열이 온다.
            if (token.equals("-")) {
                String[] split = st.nextToken().split("\\+");
                int tmp = 0;
                for (int i = 0; i < split.length; i++) {
                    tmp += Integer.parseInt(split[i]);
                }
                sum -= tmp;
            } else {
                // 문자열에 +으로만 이루어진 경우 -> ex) 10+20+30+40
                if (token.contains("+")) {
                    String[] split = token.split("\\+");
                    for (int i = 0; i < split.length; i++) {
                        sum += Integer.parseInt(split[i]);
                    }
                }
                // 숫자로만 이루어진 경우
                else {
                    sum += Integer.parseInt(token);
                }
            }
        }

        System.out.println(sum);

    }
}