백준 1541: 잃어버린 괄호

안녕하세요! 오늘은 백준의 실버 2 난이도 문제인 "잃어버린 괄호"를 풀어보겠습니다. 이 문제는 주어진 수식에서 괄호를 적절히 사용하여 결과를 최대로 만드는 방법을 찾는 문제입니다.

1. 문제 소개

• 문제 번호: 1541
• 문제명: 잃어버린 괄호
• 난이도: Silver II
• 사용 언어: C++
• 실행 시간: 0 ms
• 메모리: 2080 KB
• 문제 요약:
  주어진 수식은 빼기(-) 연산으로만 이루어져 있으며, 숫자와 빼기 연산자만으로 구성되어 있습니다. 이 수식에 괄호를 적절히 추가하여 가능한 가장 큰 값을 만들려고 합니다. 괄호는 연산 순서를 변경할 수 있습니다.

2. 접근 방법

이 문제를 해결하기 위한 핵심 아이디어는 '-' (빼기) 연산자를 기준으로 수식을 분리하고, 각 분리된 부분에서 덧셈을 최대한 수행한 후, 첫 번째 부분을 제외한 나머지 부분들을 빼주는 것입니다.

왜 이런 방법을 선택했는가?

우리는 수식의 결과값을 최대로 만들어야 합니다. 덧셈 연산은 값을 증가시키지만, 뺄셈 연산은 값을 감소시킵니다. 따라서, 뺄셈 연산이 나타나기 전까지는 모든 숫자를 더해주는 것이 가장 큰 값을 만드는 데 유리합니다.

예를 들어, 1+2-3+4-5라는 수식이 있다고 가정해봅시다.
이 수식을 뺄셈(-) 기준으로 나누면 다음과 같이 세 덩어리로 나눌 수 있습니다.

1. 1+2
2. 3+4
3. 5

이제 이 덩어리들을 가지고 결과값을 최대로 만들어 봅시다.

• 첫 번째 덩어리 (1+2)는 뺄셈 앞에 있으므로 그대로 더해줍니다. (1 + 2 = 3)
• 두 번째 덩어리 (3+4)는 첫 번째 뺄셈 뒤에 있으므로, 이 덩어리 안의 모든 합을 전체 결과에서 빼줍니다. (3 + 4 = 7)
• 세 번째 덩어리 (5)는 두 번째 뺄셈 뒤에 있으므로, 이 덩어리의 값도 전체 결과에서 빼줍니다. (5)

따라서, 최종 계산은 (1+2) - (3+4) - (5) 와 같이 됩니다.
결과적으로 3 - 7 - 5 = -9 가 됩니다.

만약 괄호를 다르게 적용한다면 1 + 2 - (3 + 4 - 5) 와 같이 될 수 있습니다. 이 경우 1 + 2 - 2 = 1 이 되어 앞선 결과보다 작습니다.

결론적으로, '-' 연산자를 만날 때마다 그 뒤에 오는 숫자 덩어리들은 모두 빼주면 된다는 규칙을 발견할 수 있습니다. 그리고 각 덩어리 안에서는 '+' 연산자로 연결된 숫자들을 모두 더해주면 됩니다.

3. 풀이 과정

1. 입력 받기: 전체 수식을 문자열 s로 입력받습니다.
2. '-' 기준으로 분리: 입력받은 문자열 s를 '-' 문자를 기준으로 여러 개의 부분 문자열로 나눕니다. 각 부분 문자열에는 숫자와 '+' 연산자만 포함됩니다. 이 부분 문자열들을 vector<string> parts에 저장합니다.
   • 예: 1+2-3+4-5 -> parts = {"1+2", "3+4", "5"}
3. 첫 번째 부분 처리: parts 벡터의 첫 번째 요소(parts[0])는 뺄셈 연산자가 앞에 없으므로, 해당 부분 문자열 내의 숫자들을 모두 더하여 ans 변수에 초기값으로 저장합니다. stringstream을 사용하여 '+' 문자를 기준으로 숫자를 분리하고 stoi() 함수로 정수 변환 후 ans에 더합니다.
4. 나머지 부분 처리: parts 벡터의 두 번째 요소부터 마지막 요소까지 (parts[1]부터) 순회합니다. 각 부분 문자열에 대해, stringstream을 사용하여 '+' 문자를 기준으로 숫자들을 분리하고 stoi() 함수로 정수 변환합니다. 이렇게 분리된 숫자들은 모두 ans에서 빼줍니다.
5. 결과 출력: 최종적으로 계산된 ans 값을 출력합니다.

핵심 아이디어

• '-' 연산자는 "분기점"입니다. 이 지점을 넘어서는 모든 덧셈 결과는 전체에서 빼야 합니다.
• 각 '-'로 분리된 덩어리 안에서는 '+' 연산자로 연결된 숫자들을 모두 더하는 것이 해당 덩어리의 최대값입니다.

주의할 점

• 마지막 덩어리는 '-'로 끝나지 않으므로, 루프가 끝난 후 마지막 tmp 값을 parts에 추가해줘야 합니다.
• stringstream과 getline을 사용하여 '+' 기준으로 문자열을 분리하는 것이 편리합니다. getline(ss, num, '+')는 ss 스트림에서 '+' 문자가 나올 때까지 num에 읽어옵니다.

4. 코드 설명

#include <bits/stdc++.h> // C++ 표준 라이브러리 헤더 포함
using namespace std;

int main() {
    string s;
    cin >> s;  // 전체 수식을 문자열로 입력받습니다.

    vector<string> parts; // '-' 기준으로 나눌 조각들을 저장할 벡터
    string tmp = "";      // '-' 기준으로 분리된 각 덩어리를 임시 저장할 변수

    // 수식을 한 글자씩 순회하며 '-'를 기준으로 분리
    for (char c : s) {
        if (c == '-') {
            parts.push_back(tmp); // '-' 이전까지의 덩어리(숫자, '+')를 parts에 추가
            tmp = "";             // 다음 덩어리를 위해 tmp 초기화
        } else {
            tmp += c;             // 숫자 또는 '+'를 현재 덩어리에 이어붙임
        }
    }
    parts.push_back(tmp); // 마지막 덩어리도 parts에 추가 (마지막에는 '-'가 없으므로 자동 추가되지 않음)

    int ans = 0; // 최종 결과를 저장할 변수

    // 첫 번째 덩어리 처리: 뺄셈 앞에 있으므로 그냥 더함
    stringstream ss(parts[0]); // 첫 번째 덩어리를 stringstream으로 처리
    string num;
    while (getline(ss, num, '+')) { // '+'를 기준으로 숫자를 분리
        ans += stoi(num);          // 분리된 숫자를 정수로 변환하여 ans에 더함
    }

    // 두 번째 덩어리부터 처리: 뺄셈 뒤에 있으므로 모두 빼줌
    for (int i = 1; i < parts.size(); i++) {
        stringstream ss2(parts[i]); // 현재 덩어리를 stringstream으로 처리
        while (getline(ss2, num, '+')) { // '+'를 기준으로 숫자를 분리
            ans -= stoi(num);          // 분리된 숫자를 정수로 변환하여 ans에서 뺌
        }
    }

    cout << ans; // 계산된 최소값 출력
    return 0;
}

주요 부분 설명

• #include <bits/stdc++.h>: 입출력, 문자열 처리, 벡터, stringstream 등 필요한 모든 라이브러리를 포함합니다.
• string s; cin >> s;: 수식을 문자열로 입력받습니다.
• vector<string> parts;: '-' 문자로 구분된 수식의 각 부분을 저장하는 벡터입니다.
• stringstream ss(parts[0]);: 첫 번째 부분 문자열(parts[0])을 stringstream 객체 ss로 만듭니다. 이를 통해 + 기호를 기준으로 숫자를 쉽게 분리할 수 있습니다.
• getline(ss, num, '+'): ss 스트림에서 + 문자를 만날 때까지의 문자열을 num 변수에 저장합니다.
• stoi(num): 문자열 num을 정수형으로 변환합니다.

코드 주석

코드 내 주석을 통해 각 줄의 역할과 로직을 상세하게 설명하였습니다.

5. 복잡도 분석

• 시간 복잡도:
  입력 문자열의 길이가 N이라고 할 때, 문자열을 순회하며 '-'를 기준으로 분리하는 과정은 O(N)입니다. 각 분리된 부분 문자열에 대해 stringstream을 사용하여 숫자를 파싱하는 과정도 전체 문자의 길이에 비례하므로 O(N)입니다. 따라서 총 시간 복잡도는 O(N) 입니다.

• 공간 복잡도:
  parts 벡터에 저장되는 문자열들의 총 길이는 입력 문자열 s의 길이 N을 넘지 않습니다. stringstream 등에서 사용하는 임시 공간도 최대 O(N)입니다. 따라서 공간 복잡도는 O(N) 입니다.

6. 배운 점

이 문제를 통해 다음 내용을 배울 수 있었습니다.

• 문자열 파싱 전략: 복잡한 문자열에서 특정 구분자(여기서는 '-')를 기준으로 데이터를 분리하고, 다시 그 안에서 다른 구분자(여기서는 '+')를 기준으로 데이터를 처리하는 방법을 효과적으로 익혔습니다. stringstream과 getline의 조합은 이러한 문자열 파싱 작업에 매우 유용합니다.
• 탐욕 알고리즘(Greedy Algorithm)의 적용: 최댓값을 만들기 위해 각 단계에서 가장 유리한 선택(뺄셈 전까지는 무조건 덧셈)을 하는 탐욕적인 접근 방식이 문제 해결에 효과적임을 알 수 있었습니다.
• 문제의 본질 파악: 단순히 코드를 작성하는 것을 넘어, 문제에서 요구하는 '최대값'을 만들기 위한 논리적 사고 과정을 거치는 것이 중요함을 다시 한번 느꼈습니다. '-'를 기준으로 묶는 아이디어가 문제의 핵심이었습니다.

이러한 문자열 처리 및 탐욕적 접근 방식은 다양한 알고리즘 문제에서 유용하게 활용될 수 있습니다. 다음 문제에서도 이 경험을 바탕으로 더 빠르고 정확하게 해결해나가겠습니다!

궁금한 점이나 다른 풀이가 있다면 댓글로 남겨주세요!
```