[C++] 백준 1541 잃어버린 괄호

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

1. 서론

이 문제는 그리디 알고리즘으로 풀 수 있다.

그리디 알고리즘이란 매 순간 최적의 방법을 선택하는 것이다.

결과적으로 최적의 방법은 아닐지 몰라도 고를 수 있는 선택지 중에서 가장 최적의 방법을 고르는 것이다.

 

2. 문제 풀이

 

'0' ~ '9', '+', '-' 로만 이루어진 식이 있다. 이 식은 전부 문자열로 입력된다.

이 식에 적절히 괄호를 쳐서 값을 최소로 만드는 코드를 짜야한다. 

 

예제로 예를 들자면

 

'55-50+40'

 

이라는 식이 있다. 

 

55-(50+40)

 

이렇게 괄호를 치면 값이 -35로 가장 최소의 값이 나온다.

 

어디에다 어떻게 괄호를 쳐야 가장 최소의 값이 나올까 아이디어에 대해 고민을 했다.

그 결과 '-' 뒤에 무조건 괄호를 쳐야 한다는 것을 깨달았다. 예제 말고도 생각한 테스트 케이스로 예를 들자면

 

'35+48-50+4-20'

 

이런 식이 있다. 예제와는 달리 '-'가 두 번 있다. 최소의 값을 구하려면 최대한 많은 수가 빼 져야 한다고 생각했다.

 

35+48-(50+4)-20

 

이렇게 하면 총 -74가 되니까 최소의 값이 된다.

아이디어는 이렇게 간단하다. '-'가 나오면 괄호를 열고 다음 '-'가 나올 때까지 기다린 후 괄호를 닫는다. 

 

3. 코드 설명

 

- mordern C++ (stoi 함수 쓴 경우)

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s, tmp;
    int i, j = 0,c = 0, sum[50], x = 0, y = 0, f = 0;

    getline(cin, s);

    for (i = 0; s[i] != '\0'; i++)
    {
        if (s[i + 1] == '-' || s[i + 1] == '+' || s[i + 1] == '\0')
        {
            tmp = s.substr(c, i + 1 - c);
            c = i + 2;
            sum[j++] = stoi(tmp);

            if (s[i + 1] == '-')
                sum[j++] = -1;
        }
    }

    for (i = 0; i < j; i++)
    {
        if (sum[i] != -1)
        {
            if (f == 0)
                x += sum[i];
            
            if (f == 1)
            {
                y += sum[i];
                if (i + 1 == j) 
                {
                    x = x + (y * -1);
                    y = 0;
                    f = 0;
                }
            }
        }

         if (sum[i] == -1 && f == 0)
            f = 1;
    }

    cout << x << endl;
}

 

처음에는 이렇게 풀었었다. 당연히 맞았지만 C++11 이상부터 맞았고 그냥 C++ 에선 stoi 함수 때문에 컴파일 에러가 났다.

그래서 stoi함수 부분을 코드로 구현해서 코드를 바꿨다.

 

-C++ (stoi 함수 안 쓴 경우)

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

//stoi 함수 구현
int calc(string s)
{
    int i, sum = 0, mul = 1;

    for (i = s.size() - 1; i >= 0; i--)
    {
        sum += (s[i] - '0') * mul;
        mul *= 10;
    }

    return sum;

}
int main()
{
    string s, tmp;
    int i, j = 0,c = 0, sum[50], x = 0, y = 0, f = 0;

	//문자열 공백까지 전부 입력받음 (iostream)
    getline(cin, s);

    for (i = 0; s[i] != '\0'; i++)
    {
        if (s[i + 1] == '-' || s[i + 1] == '+' || s[i + 1] == '\0')
        {
        	//문자열 추출 해당 인덱스부터 n개의 항목까지 선택 (string)
            tmp = s.substr(c, i + 1 - c);
            c = i + 2;
            sum[j++] = calc(tmp);

            if (s[i + 1] == '-')
                sum[j++] = -1;
        }
    }

    for (i = 0; i < j; i++)
    {
        if (sum[i] != -1)
        {
            if (f == 0)
                x += sum[i];
            
            if (f == 1)
            {
                y += sum[i];
                if (i + 1 == j) 
                {
                    x = x + (y * -1);
                    y = 0;
                    f = 0;
                }
            }
        }

         if (sum[i] == -1 && f == 0)
            f = 1;
    }

    cout << x << endl;
}

 

이거 보다 쉽고 좋게 푸는 방법이 있을 것 같은데 생각이 안 나서 일단 이렇게 풀었다.

 

문자열로 식을 입력받은 후, 문자열에서 '+', '-'를 기준으로 문자를 잘라내서 숫자로 만들어줬다. 

그걸 각각 배열에 넣고, '-'인 경우에는 -1을 배열에 넣어줬다. 기준점으로 삼아서 계산하기 위해서이다.

 

배열의 값을 x에다가 계속 더한다. 만약에 배열에서 값으로 -1이 나오면 f를 1로 바꾸고, 그 이후의 값을 y에 계속 더한다.

그리고 마지막에 x와 y를 더하는데 y에 -1을 곱해서 계산해준다.

 

풀이를 적다가 깨달았는데 어떤 식이 와도 '-'가 나온 순간부터 식의 끝까지 괄호를 쳐서 계산해도 답이 된다.

내가 식을 그렇게 짜고도 몰랐다. '-'가 나올때마다 사이사이에 괄호를 쳐줘야 한다고 생각했는데 그냥

 

35+48-(50+4-20)

 

이렇게 해도 아무상관 없다.

 

35+48-(50+4-20+1)

 

뒤에 '-'가 붙으나 '+'가 붙으나 아무 상관이 없다 괄호만 치면 다 '-'로 엮을 수 있으니까...

그러면 식을 더 간단히 고칠 수도 있을 것 같은데 귀찮아서 그냥 두련다.... ㅎ