백준 - 1541 잃어버린 괄호

문제 링크

greedy 문제이다. 풀이는 간단하다. 괄호 개수의 제한이 없기 때문에 '-'를 만나면, 다음 '-'를 만날 때까지 그 값들을 전부 더한 뒤 계산 값에서 빼주면 된다.

왜냐하면 괄호 앞에 '-'가 있을 경우, 분배 법칙으로 괄호 안의 양수 값들은 전부 '-'로 처리되기 때문이다. 

나는 처음에 '-'를 토큰으로 문자열을 전부 나눈 뒤, 전부 덧셈 연산 처리를 한 다음에 빼줘서 풀었다.

하지만 그럴 필요 없이 그냥 값들을 전부 더해주다가 '-'를 만나면 그때부터 전부 다 빼주면 된다. 어차피 첫 '-'뒤의 '+'들은 전부 분배 법칙으로 '-'가 될 것이며, 다음 '-'를 만나면 그 전에 괄호를 닫고 다시 열게 되기 때문이다.

우선 처음에 그냥 '-'를 기준으로 토큰을 나눈 뒤 풀었던 코드이다. 나눈 토큰 들을 '+'처리한 다음에 첫 문자열을 제외한 나머지 문자열들은 전부 빼줬다.

//-가 나오면, 그 때부터 다음 -가 나올때까지 전부다 괄호를 쳐버리면 된다.
//-를 토큰으로 문자열을 추출한다. 그 문자열 안에 있는 값들의 +연산을 모두 처리하면 된다. 
#include <cstdio>
#include <cstring>
#include <cstdlib>
char cal[51] = { 0, };
char ca[51][51] = {0,};
char* ptr;
int ret,i=0;
//+연산을 처리하는 함수 
int calculate(char* str) {
    int r = 0;
    char* ptr2;
    ptr2 = strtok(str, "+");
    r += atoi(ptr2);
    while (ptr2 = strtok(NULL, "+")) {
        r += atoi(ptr2);
    }
    return r;
}
int main() {
    scanf("%s", cal);
    //-를 토큰으로 분해하고, 각 문자열을 저장한다. 
    ptr = strtok(cal, "-");
    strcpy(ca[i++],ptr);
    while (ptr = strtok(NULL, "-")) {
        strcpy(ca[i++],ptr);
    }
    //분해한 문자열을 전부 +연산 처리를 하고, 첫 수를 제외한 나머지 수는 전부 뺄셈 처리를 한다. 
    ret=calculate(ca[0]);
    for(int j=1;j<i;j++){
        ret -= calculate(ca[j]);
    }
    printf("%d",ret);
}

이 코드만 봐도 알고 보면 첫 '-'이후의 값들은 전부 다 빼주면 된다는 걸 알 수 있다.

다음 코드는 이를 적용해 보았다.

#include <cstdio>
#include <cstring>
#include <cstdlib>
char cal[51] = { 0, };
char ca[51] = {0,};
char* ptr;
int ret,i=0;
//덧셈을 처리하는 함수. 전과 달라진건 -,+을 안가리고 전부 더해버린다. 
int calculate(char* str) {
    int r = 0;
    char* ptr2;
    ptr2 = strtok(str, "+-");
    r += atoi(ptr2);
    while (ptr2 = strtok(NULL, "+-")) {
        r += atoi(ptr2);
    }
    return r;
}
int main() {
    scanf("%s", cal);
    //첫 -를 기준으로 토큰을 나눈다. 
    ptr = strtok(cal, "-");
    strcpy(ca,ptr);
    //첫 - 이후의 문자열을 받는다. 
    ptr = strtok(NULL,"");  
    ret=calculate(ca);
    //첫 - 이후의 문자열은 전부 덧셈 처리한 뒤 빼준다. 
    if(ptr!=NULL)ret-=calculate(ptr); 
    printf("%d",ret);
}

마지막으로는 다른 분 코드를 참조해 짜본, 라이브러리 함수를 쓰지 않고 배열을 하나하나 검사해서 짜는 코드이다.

#include <cstdio>
char cal[51] = { 0, };
int ret=0,n=0,i=0,flag=0;
int main() {
    scanf("%s", cal);
    while(cal[i] != 0){
        //숫자이면 
        if(cal[i] >='0' && cal[i]<='9'){
            //이전에 저장한 숫자의 자릿수를 하나 늘려주고 이 값을 더해준다. 
            n*=10;
            n+=cal[i]-'0'; 
        }
        //그 후 지금까지 숫자값들을 0으로 초기화해준다. 
        else{
            //-연산자를 만난적이 없으면, 즉 flag가 0이면 그냥 더해준다.
            if(flag==0) ret +=n;
            //-연산자를 만난적이 있으면, 즉 flag가 1이면 뺄셈처리한다.
            else ret-=n;
            //첫 -이면, 즉 -이고 flag가 0이면 flag를 1로 만들어준다. 
            if(cal[i]=='-'&&flag==0) flag=1;
            n = 0; 
        } 
        i++;
    }
    //마지막 숫자를 flag에 맞게 처리해준다. 
    if(flag==0) ret+=n;
    else if(flag==1) ret-=n;
    printf("%d",ret);
}