[PS/BOJ] 1541번. 잃어버린 괄호 - C++[cpp]

문제

 

이 문제는 문자열 처리와 식의 값을 최소로 만드는 방법을 요구하고 있다.

아이디어

나올 수 있는 경우의 수를 생각해보자.

• 1 + 2 + 3 + 4 -> 그대로 더한다.
• 1 - 2 - 3 - 4 -> 그대로 뺀다.
• 1 - 2 + 3 - 4
  • -> (2 + 3)을 묶어버린다 
  • 1 - (2 + 3) - 4 = 1 - 2 - 3 - 4
  • 즉, - 가 한 번 나온 뒤로, 그 뒤에 오는 모든 수는 다 빼주면 된다.

코드(중요!)

아이디어는 대부분 다 떠올렸겠지만, 문자열 처리를 어떻게 할 지 고민인 분들이 많을 것이다.

이 부분이 이 글을 쓰는 이유이기도 한데,

구글링해서 나오는 코드 대부분은 아래와 같이 문자를 하나씩 입력받아 숫자, 연산자를 구분하고 있다.

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string input;
    cin >> input;
 
    int result = 0;
    string num;
    bool isMinus = false;
 
    for (int i = 0; i <= input.size(); i++) {
        
        if (input[i] == '-' || input[i] == '+' || i==input.size()) {
            if (isMinus) {
                result -= stoi(num);
                num = "";
            }
            else {
                result += stoi(num);
                num = "";
            }
        }
        else {
            num += input[i];
        }
 
        if (input[i] == '-') {
            isMinus = true;
        }    
    }
    
    cout << result;
}

 

사실 PS 환경에서는 위와 같이 구현할 필요가 없다. 이미 입력의 종료가 정해져있기 때문에 cin >> 의 반환값으로 입력의 종료를 알 수 있다. 아래 코드를 확인해보자.

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

int main(void) {
    cin.tie(0)->sync_with_stdio(false);
    int x; char c;
    
    // 첫 번째 숫자 입력 받기
    cin >> x;
    int sum = x;
    
    // 처음 minus가 등장한 이후로 minus는 true가 된다.
    bool minus = false;
    while (cin >> c) { // 연산자
        cin >> x; // 정수
        if (c == '-') minus = true; // minus 최초 등장
        if (minus) sum -= x; // minus가 등장했었다면 무조건 뺀다.
        else sum += x; // 등장하지 않았다면 더한다.
    }
    cout << sum;
}

 

문제에서 숫자가 먼저 등장한다고 조건을 주었다. 첫 번째 숫자가 등장하고, {연산자, 숫자} 패턴이 반복된다. 즉, 첫 번째 숫자를 먼저 읽고, 나머지 세트를 계속해서 받으면 된다.

 

cin의 대상이 되는 타입이 정수면, cin은 정확히 정수까지만 읽어준다. 그래서 cin >> x를 하면

55-50+40

 

에서 55까지만 읽어서 저장해준다.

 

이제 {연산자, 숫자} 세트를 읽어줄텐데 이 역시 마찬가지로 cin의 대상이 char이면 문자 부분만 읽어준다. 

그래서 cin >> c 를 하면 c가 char라 '-'만 읽고, 그 다음에 cin >> x를 하면 x가 int라 50을 읽는다.

 

이 원리를 알면, 코드를 매우 짧게 작성할 수 있다.