[백준] 1541 잃어버린 괄호

Posted on | In

그리디 문제는 쉬운 것 같으면서도 항상 쉽지가 않다. 오잉 이거 그냥 이렇게 푸는 거 아니야? 해서 쉽게 풀리는 문제가 있는가 하면 이 문제처럼 아무리 헤매고 헤매도 방법이 슉 안 떠올라서 고생하는 문제가 있다. 슥슥 안 풀렸던 문제이기 때문에, 기록을 남기려고 이렇게 블로그 포스팅을 한다!

문제 설명

링크 : 1541_잃어버린_괄호

이 문제는 주어진 식에서 적절히 괄호를 해서 식의 최솟값을 구하는 문제이다. 문제 자체에 대해서는 별로 어려울 게 없지만, 이 문제를 풀려고 생각해 보면 하나 둘씩 어려운 점이 나타나기 시작한다. 식이 부호와 띄어쓰기 없이 숫자와 같이 주루루룩 주어지기 때문에 나는 처음 봤을 때 이 string 식을 계산할 수 있는 형태로 바꾸는 것부터 고민이 많았다. 이것은 for문에서 i번째로 하나씩 읽으면서, 만약 + - 부호가 아니라면 num 이라는 새로운 string에 더해 주는 식으로 해서 해결할 수 있다.

문제 풀이

나는 풀다풀다 너무 모르겠어서 요 링크를 참고해서 풀었다. 문제_풀이_링크 정말… 그리디 문제든 뭐든 이렇게 쉽게 풀어내는 풀이들을 보면 경이롭다.

1. 내가 생각한 풀이

나는 그리디 문제라는 걸 인지했음에도 이 문제를 어떻게 풀어야 할지 감이 안 잡혔다. 그리디가 그 순간 최대를 선택하는 것이므로.. 나는 - 를 기준으로 식을 두 개로 나누어서 계산해본 후 최소를 구해야 한다고 생각했다. 만약 55-50+40-30+10 이라면 (55)-(50+40-30+10) 과 (55-50+40)-(30+10) 을 비교해서 그 중 더 최소인 것들을 골라야 한다고 생각했다. (마이너스가 두개이므로) 그리고 저 괄호 안의 애들을 재귀로 다시 돌려서 괄호 안의 최솟값을 구하는? 형태로 생각했었다. 접근 자체는 나름대로 의미 있었다고 생각했으나, 나의 최대 관문은 저 string을 어떻게 숫자와 수식으로 바꿔서 계산하느냐였다. 만약 + - 없이 숫자 input만 받았다면 그냥 stoi를 return 하도록 했고, 수식이 껴 있다면 또 다시 재귀,, 이런 식으로 했는데 어디선가 segmentation fault가 자꾸 나서 이렇게 푸는 걸 포기했었다. 나는 string ‘111’과 ‘11’을 숫자로 바꾸기 위해 막 길이를 입력 받고, 10을 길이만큼 곱해 주고.. 이런 과정을 하기가 너무 싫었다. 코드가 복잡해지는 것 같았다. 아무튼 나는 이런 방법을 시도했었다.

2. 문제 풀이

아무튼,, 풀이를 설명해 보자면 string 인풋으로 수식을 입력 받는다. 보통 나는 cstdio 헤더를 쓰는데, 이렇게 문자열을 받을 때는 scanf가 까다로워서 그냥 iostream 헤더를 써서 cin을 쓴다. 이렇게 입력받은 string을 한 글자씩 흝으면서 부호인지 아니면 숫자인지를 판별해야 한다. 이 문제가 string 숫자 ‘111’을 111로 바꿨던 방법이 나에게는 굉장히 획기적이었다. 일단 하나씩 흝으면서 +-가 나오면 숫자가 끝났다는 이야기이다. +-가 나오지 않는다면 숫자라는 말이기 때문에, 새로운 num이라는 string에 계속해서 한글자씩 더해준다. 그리고 +-가 나온 순간, 즉 숫자가 끝나는 순간 이 num이라는 string을 stoi를 이용해 숫자로 바꾼 후 계산에 이용하면 된다. 이용 후에는, 이 num string을 초기화해주면 된다. 그럼 이제 계산할 부호를 살펴보아야 한다. 이 부분이 그리디가 되는 중요한 부분이기는 하다 ㅎㅎ

-가 나왔다는 이야기는, 그 뒤에 +가 몇개가 나오건 -가 몇개가 나오건 + - 가 섞여서 나오건 모두 그 뒤에 나오는 숫자들에 대해 모두 뺄셈 처리를 해줄 수 있다는 이야기이다.

잘 생각해보면, - 뒤에 +만 주구장창 나왔을 경우에는 - 뒤의 수식을 괄호로 묶어서 모두 -처리가 가능해진다. -(숫자)뒤에 또 -가 나왔을 떄는, 첫번째 -뒤의 숫자 하나에만 괄호를 해주면(결국 괄호하지 않은 것이랑 똑같다) - 뒤의 숫자들을 모두 - 처리해줄 수 있다. -와 +가 섞여 나오는 경우도, 괄호를 적절히 배치하면 숫자들을 모두 음수로 만들어 줄 수 있다! 너무 놀라운 발상이다. 아무튼 이렇기 때문에, -가 나오기 전까지는 숫자들을 위의 string num으로 잘 받아서 더해 주다가 -가 나오기 시작하면 위의 string num으로 잘 받은 애들을 빼 주기 시작하면 된다.

코드를 첨부하였다.

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
#include <iostream>
#include <string.h>
using namespace std;

int main(){
    string s;
    cin>>s;

    string n;
    bool isMinus=false;
    int ans=0;
    for(int i=0;i<=s.size();i++){
        if(s[i]=='+' || s[i]=='-' || i==s.size()){
            if(isMinus) ans-=stoi(n);
            else ans+=stoi(n);

            // n 초기화
            n="";
        }
        else{
            n+=s[i];
        }

        if(s[i]=='-') isMinus=true;
    }
    cout<<ans<<endl;
}