백준 1541번 [잃어버린 괄호](C++) -yes6686- 티스토리

백준 문제 풀이: 1541 [잃어버린 괄호]

---

문제 링크: https://www.acmicpc.net/problem/1541

문제 설명:

주어진 식에서 괄호를 적절히 배치하여 최소값을 만드는 프로그램을 작성하세요.

입력 조건:

• 식은 '0-9', '+', '-'로만 이루어져 있으며, 가장 처음과 마지막 문자는 숫자입니다.
• 식의 길이는 50을 넘지 않습니다.

출력 조건:

• 괄호를 적절히 배치하여 식의 최소값을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

int main() {
    string n;
    cin >> n;

    int sum = 0; // 최종 결과 값
    int current = 0; // 현재 숫자 저장
    bool subtract = false; // '-' 이후로는 모두 빼기

    for (int i = 0; i <= n.size(); i++) {
        if (n[i] == '+' || n[i] == '-' || i == n.size()) {
            // 숫자를 sum에 반영
            if (subtract) {
                sum -= current;
            } else {
                sum += current;
            }
            current = 0; // 현재 숫자 초기화

            if (n[i] == '-') {
                subtract = true; // '-' 이후부터 빼기 시작
            }
        } else {
            // 숫자를 계산
            current = current * 10 + (n[i] - '0');
        }
    }

    cout << sum << '\n';
    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 '-' 기호를 기준으로 그룹을 나누고, 첫 '-' 이후에는 모든 숫자를 뺍니다. 이를 통해 최소값을 구할 수 있습니다.

• 문자열 순회:
  • 숫자와 연산자를 구분하여 처리합니다.
• 그룹별 계산:
  • '-'가 등장하기 전까지는 숫자를 더하고, 이후부터는 모두 뺍니다.

시간 복잡도 분석:

• 문자열을 한 번 순회하며 계산하므로 O(n).

입력의 길이가 최대 50이므로 매우 효율적으로 동작합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
55-50+40

출력:
-35

입력:
10+20+30-40+50-60

출력:
-90

주어진 식에서 최소값을 계산하여 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!