[C++] Baekjoon 1541번: 잃어버린 괄호

1. 문제

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

숫자와 부호들이 번갈아 가면서 등장하는데, 적절하게 괄호를 쳐서 만들 수 있는 최솟값을 구하면 된다.

가장 처음과 마지막은 숫자이고, 연속해서 두 개 이상의 연산자가 나타나지는 않는다.

예외처리는 고려하지 않아도 될 것 같다.

2. 풀이

 
마이너스가 한 번이라도 등장하면 그 뒤는 괄호 쳐서 다 마이너스 처리하면 되는 거 아닌가? 라고 생각했다.

여기까지는 쉽게 생각했는데 문제는 문자열로 입력받은 것을 어떻게 숫자와 기호로 구분할 수 있는가였다.

 

처음 든 생각은 숫자형 문자에 - '0'을 해주는 것이었다.

 

0의 ASCII 값이 48이기 때문에 어떤 숫자형 문자에 - '0'을 해주면 해당 숫자가 된다.

 

옛날에 42서울을 하면서 이런 식으로 풀이하는 것이 익숙해져서인지 이 방법이 먼저 떠올랐는데,

 

이 방법은 자릿수도 고려해줘야 할 것 같아서 어지러웠다. 그래서 그냥 편하게 stoi를 이용하기로 했다. 

 

마이너스가 한 번이라도 등장하면, 마이너스 뒤의 숫자들은 다 빼주면 된다!

 

3. 코드

#include <iostream>

#include <string>

using namespace std;

int main() {

    string str; // 입력 받은 문자열(식)

    string num = ""; // 문자열 중에 숫자 부분을 따로 저장

    bool flag = false; // 마이너스가 한번이라도 등장했는지 판단

    int res = 0; // 결과값(최소값)

    cin >> str;

    for (int i = 0; i <= str.size(); i++) {

        if (flag == false) { // 한 번도 마이너스가 나온 적 없을때

            if (str[i] == '+' || str[i] == '-' || i == str.size()) { // 부호 혹은 문자열 끝을 만났을떄

                if (str[i] == '+') {

                    res += stoi(num); //stoi 를 사용해서 문자열을 해당하는 숫자로 변환

                    num = ""; // 숫자 문자열 초기화

                }

                else if (str[i] == '-') { // 마이너스가 한번이라도 등장했다면

                    res += stoi(num); // 지금까지 나온건 일단 더해주고 (마이너스 앞 부분)

                    flag = true; // flag 를 true로 변경 (이 뒤에 나오는건 다 마이너스 연산하기 위함)

                    num = ""; // 숫자 문자열 초기화

                }

                else if (i == str.size()) { // 종료조건

                    res += stoi(num); // 마지막 숫자까지 계산

                }

            }

            else {

                num += str[i]; // 부호나 문자열의 끝이 아니라면 숫자이므로 숫자 문자열에 저장

            }

        }

        else { // 음수가 한번이라도 등장해서 flag가 true가 된 경우

            if (str[i] == '+' || str[i] == '-' || i == str.size()) {

                if (i == str.size()) { // 끝이면 마지막 숫자 빼기

                    res -= stoi(num);

                }

                else { // 끝이 아닌 모든 경우 마이너스 연산 수행 해주면 됨

                    res -= stoi(num);

                    num = "";

                }

            }

            else

                num += str[i];

        }

    }

    cout << res;

    return 0;

}

 

4. 느낀점

알고리즘 분류에 그리디 알고리즘이라고 되어있었는데

 

음... 사실 그리디 알고리즘을 활용해서 풀었는지는 잘 모르겠다.

 

지금 상황에서 최선의 선택을 하다 보니 해답을 찾을 수 있는 문제긴 했는데

 

사실 그리디 알고리즘보다는 문자열 파싱과 간단한 수학적 사고가 더 중요했던 문제였다.

 

stoi를 활용할 수 있었고, C++에서는 문자열의 끝을 '\0' 이 아니라 str.size()와 같은 값으로 판단해야 한다는 것을 알게 되었다.

 

std::string 클래스를 잘 활용하자!

 

오늘 하루도 쌓였다!