백준 1541 잃어버린 괄호

1. 문제 정리

1.1 문제 개요

세준이는 양수와 ’+’, ’-’ 연산자 그리고 괄호를 사용해 하나의 식을 만들었습니다.

그러나 나중에 세준이는 식에서 모든 괄호를 지워버렸습니다.

이제 세준이는 원래의 식에 괄호를 적절히 추가하여 최소 결과값을 만들어 내고자 합니다.

즉, 괄호의 배치를 잘 조정하여 식의 계산 결과가 최소가 되는 값을 구하는 문제입니다.

1.2 입력 조건

• 입력 형식: 한 줄로 구성된 수식
• 수식 구성:
  • 0부터 9까지의 숫자
  • '+', '-' 기호
• 제약 사항:
  • 식의 첫 번째와 마지막 문자는 반드시 숫자이다.
  • 연속해서 두 개 이상의 연산자가 등장하지 않는다.
  • 한 숫자가 5자리를 초과하지 않는다.
  • 숫자는 선행하는 0을 포함할 수 있다.
  • 식의 길이는 최대 50자이다.
• 괄호를 적절히 추가하여 계산했을 때의 최소 결과값을 출력합니다.

1.4 예제

• 예제 1
  • 입력: 55-50+40
  • 출력: 35
• 예제 2
  • 입력: 10+20+30+40
  • 출력: 100
• 예제 3
  • 입력: 00009-00009
  • 출력: 0

2. 코드 설명

2.1 C++ 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <iostream>
#include <string>

int main()
{
    std::string expression;
    std::cin >> expression;

    int sum = 0;
    bool isMinus = false;  // 처음 '-'가 나왔는지 여부를 판단하는 플래그
    std::string number;    // 현재까지 누적된 숫자를 저장하는 문자열

    // 식을 한 글자씩 순회하며 처리
    for (char c : expression)
    {
        // 연산자 '+' 또는 '-'를 만났을 때
        if (c == '+' || c == '-')
        {
            // '-' 이후부터 등장하는 숫자는 빼줌
            if (isMinus)
            {
                sum -= std::stoi(number);
            }
            // 아직 '-'가 나오지 않은 상태이고, 현재 연산자가 '+'인 경우
            else if (c == '+')
            {
                sum += std::stoi(number);
            }
            // 처음 '-' 연산자가 등장한 경우
            else if (c == '-')
            {
                isMinus = true;
                sum += std::stoi(number);
            }

            number.clear();  // 다음 숫자 입력을 위해 초기화
        }
        // 현재 문자가 숫자인 경우, number에 누적
        else
        {
            number.push_back(c);
        }
    }

    // 마지막에 남은 숫자 처리
    if (isMinus)
    {
        sum -= std::stoi(number);
    }
    else
    {
        sum += std::stoi(number);
    }

    std::cout << sum;

    return 0;
}

2.2 코드 동작 설명

1. 입력 및 변수 초기화
   • expression: 입력받은 수식을 저장하는 문자열입니다.
   • sum: 최종 결과값을 누적할 변수입니다.
   • isMinus: 처음 '-' 연산자가 등장했는지 여부를 나타내는 불리언 변수입니다.
   • number: 현재까지 연속된 숫자를 문자열 형태로 누적하기 위한 변수입니다.
2. 문자열 순회 및 처리
   • 식을 한 글자씩 순회하면서,
     • 연산자('+' 또는 '-')를 만났을 때:
       • 현재까지 누적된 문자열 number를 정수로 변환하여 처리합니다.
       • isMinus 플래그에 따라,
         • 이미 '-'가 등장한 경우: 해당 숫자를 빼준다.
         • 그렇지 않은 경우,
           • 현재 연산자가 '+'라면 더해준다.
           • 현재 연산자가 '-'라면 첫 번째 ‘-‘로 간주하고, 해당 숫자를 더한 후 isMinus를 true로 설정합니다.
       • 연산자 처리 후, number를 초기화하여 다음 숫자 처리를 준비합니다.
     • 숫자일 경우:
       • number에 해당 숫자를 계속 누적합니다.
3. 마지막 숫자 처리 및 결과 출력
   • 반복문이 종료된 후, 남아있는 number에 대해 같은 조건에 따라 처리합니다.
   • 최종적으로 누적된 sum 값을 출력합니다.

3. 알고리즘 설명

3.1 핵심 아이디어 및 전략

• 핵심 아이디어:

  입력된 식에서 첫 번째 '-' 이후의 모든 연산은 결과값을 최소화하기 위해 빼야 합니다.

  더하기가 많을 수록 결과가 커지기 때문에, 첫 번째 '-'가 등장한 후부터 모든 숫자들을 앞에서 더한 합에서 빼도록 괄호 처리해야 합니다.

• 전략:

  1. 첫 번째 '-' 전까지의 숫자들:
     • 이 구간에서는 '+'만 있으므로 모든 숫자를 단순히 더합니다.
  2. 첫 번째 '-' 이후부터의 숫자들:
     • 이때부터 등장하는 모든 숫자는 이전에 더한 숫자들의 합에서 빼줍니다.
  3. 이를 위해 식을 한 번 순회하면서,
     • '+'나 '-'가 등장할 때마다 현재까지 누적된 숫자를 정수로 변환하고,
     • isMinus 플래그를 사용하여 해당 숫자를 더할지 빼줄지 결정합니다.

3.2 시간 복잡도 및 공간 복잡도 분석

• 시간 복잡도:

  식의 길이를 n이라 할 때, 한 번의 순회(O(n))로 모든 문자를 처리합니다.

• 공간 복잡도:

  사용되는 변수들은 몇 개의 정수형, 불리언형, 그리고 문자열 변수 정도이므로, 추가적인 공간 복잡도는 O(1)입니다.