[0620] 알고리즘

1541. 잃어버린 괄호

  또다시 그리디 알고리즘 문제, 인데 딱히 그리디 알고리즘이라는 자각을 가지고 푼 건 아닌 것 같다. C++을 잡은 이래로 파싱을 다루는 건 아마 처음이라 좀 애먹었고... 애초에 생각했던 파싱 방법은 사용하지도 않았음(너무 복잡했었다.)

 

#include <iostream>
#include <algorithm>
#include <string>

int main()
{
    std::cin.tie(NULL);

    std::string f;

    std::cin >> f;

    int sum = 0, num = 0;
    bool cal = false;

    //cal => 앞에 마이너스가 등장했는가?
    for (int i = 0; i < f.length(); i++)
    {       
        if (f[i] == '+')
        {
            if (cal)
            {
                sum -= num;
                num = 0;
            }
            else if (!cal)
            {
                sum += num;
                num = 0;
            }
        }
        else if (f[i] == '-')
        {
            if (cal)
            {
                sum -= num;
                num = 0;
            }
            else if (!cal)
            {
                sum += num;
                num = 0;

                cal = true;
            }
        }
        else //숫자
        {
            num *= 10;
            num += (f[i] - '0');
        }
    }

    if (cal)
    {
        sum -= num;
    }
    else sum += num;

    std::cout << sum << '\n';

    return 0;
}

  일단 이 문제는 '수식에 적당히 괄호를 쳐서 가능한 한 많이 빼도록 만들기' 정도로 이해했다. 가장 작은 수를 만드려면 그렇게 해야하기 때문에... 그렇기에 빼기 기호가 나타났음을 알리는 bool 변수를 만들었다. 지금 생각해보니 어차피 한 번 빼기가 등장하면 그 이후는 어떻게든 괄호를 쳐서 빼기로 만들 수 있기 때문에... 처음 오는 -의 위치가 중요했던 것 같다.

 

  파싱... 처음 생각했던 방법은

 

1. 숫자가 등장하면 그 때부터 숫자의 자릿수를 기록한다.

2. 숫자가 더이상 등장하지 않으면 기록한 자릿수를 이용해 해당 문자열을 substr로 자른다.

3. 자른 문자열을 stoi(string을 int로 바꿈)로 int화하고 계산한다.

 

  였는데 복잡하기 그지 없었다... 그래서 타 코드를 참조했는데, 왠걸 그냥 아스키 코드 값을 이용해서 숫자를 받고 숫자가 추가될 때마다 10을 곱해서 자릿수까지 해결하는게 아닌가(...) 아스키 코드 이용하는 방법은 C언어 수업 때도 배웠었는데 미처 그걸 생각 못했었다.

 

  아무튼 n일만에 하나 해결...