[백준] 1541번 - 잃어버린 괄호 [Java][C++]

문제 링크

---

1. 문제 풀이

$+$, $-$, $0$ ~ $9$ 로 이루어진 문자열에서 괄호를 적절하게 쳐서 식의 최솟값을 만들어야 하는 문제로 연산자는 연속으로 두 개 이상 나타나지 않고 가장 처음과 마지막 문자는 숫자이다. 괄호를 어떻게 쳐야 식이 최솟값이 되는지가 중요한데 괄호 앞에 $-$ 가 붙으면 괄호 안의 연산자가 뒤바뀐다는게 포인트다.

$A + B - C + D + E - F + G$ 라는 식이 주어졌을 경우 괄호를 $A + B - (C + D + E) - (F + G)$ 이렇게 $-$ 가 등장한 순간 쳐서 다음 $-$ 가 등장하기 전에 닫으면 $+$ 를 해야했던 게 $-$ 를 하게 되어 식의 값이 최소가 된다.

---

2. 코드

1. 파싱 [Java]

StringTokenizer 를 활용해 먼저 주어진 식을 $-$ 를 기준으로 파싱했고 $+$ 와 숫자로 이루어진 식의 값을 반환하는 메서드 sum 을 통해 첫 식의 값에서 나머지 식의 값을 빼주는 방식으로 구현했다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), "-");

        int ans = sum(st.nextToken());

        while (st.hasMoreTokens()) {
            ans -= sum(st.nextToken());
        }

        System.out.println(ans);
    }

    // 숫자와 +로만 이루어진 식의 합 리턴
    static int sum(String token) {
        StringTokenizer st = new StringTokenizer(token, "+");

        int sum = 0;
        while (st.hasMoreTokens()) {
            sum += Integer.parseInt(st.nextToken());
        }

        return sum;
    }
}

2. 파싱 [C++]

string 에 대해 등장한 문자를 비교하며 파싱했다.

#include <bits/stdc++.h>
using namespace std;

// 숫자와 +로만 이루어진 식의 합 리턴
int sum(const string& s) {
    vector<string> v;
    string cur;
    for (char c : s) {
        if (c == '+') {
            v.push_back(cur);
            cur.clear();
        } else {
            cur += c;
        }
    }
    v.push_back(cur);

    int res = 0;
    for (string x : v) {
        res += stoi(x);
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    vector<string> v;
    string cur;
    for (char c : s) {
        if (c == '-') {
            v.push_back(cur);
            cur.clear();
        } else {
            cur += c;
        }
    }
    v.push_back(cur);

    int ans = sum(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ans -= sum(v[i]);
    }

    cout << ans;
}

---

3. 풀이 정보

1. 파싱 [Java]

언어	시간	메모리	코드 길이
Java 11	108 ms	14228 KB	748 B

2. 파싱 [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2024 KB	870 B

---