[C] 백준 16637번 : 괄호 추가하기

문제

 

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

 

입력

 

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

 

출력

 

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.

 

풀이

 

#include <stdio.h>
#include <math.h>
#include <limits.h>
 
using namespace std;
 
char expression_operator[10];
int N;
int ans = INT_MIN;
 
class Node{
    public:
    int val;
    Node* next;
    Node* prev;
};
 
Node* head;
Node* tail;
 
int main(){
    head = new Node();
    tail = new Node();
    
    head->next = tail;  
    tail->prev = head;
 
    scanf("%d",&N);
    char expression[20];
    scanf("%s",expression);
 
    for(int i = 0 ; i < N ; i++){
        if(i%2==0){
            Node* tmp = new Node();
            tmp->val = expression[i]-'0';
            tmp->next = tail;
            tmp->prev = tail->prev;
            tail->prev->next = tmp;
            tail->prev = tmp;
        }
        else expression_operator[i/2]=expression[i];
    }
 
    int binary = 0;
    int end = pow(2,N/2)-1;
    while(binary<=end){
        int t=binary;
        int priority[10];
        for(int i = 0 ; i < N/2 ; i++){
            priority[i] = t%2;
            t /= 2;
        }
 
        bool stop = false;
        for(int i = 0 ; i < N/2-1 ; i++){
            if(priority[i]==1 && priority[i+1]==1){
                stop = true;
                binary++;
                break;
            }
        }
        if(stop) continue;
 
        // copy linked list
        Node* ptr = head;
        Node* head_cpy = new Node();
        Node* tail_cpy = new Node();
 
        head_cpy->next = tail_cpy;
        tail_cpy->prev = head_cpy;
 
        while(ptr->next != tail){
            Node* nNode = new Node();
            nNode->val = ptr->next->val;
            nNode->next = tail_cpy;
            nNode->prev = tail_cpy->prev;
            tail_cpy->prev->next = nNode;
            tail_cpy->prev = nNode;
            ptr = ptr->next;
        }
 
        // order operator
        char operator_order[10];
        int idx=0;
        for(int i = 0 ; i < N/2 ; i++){
            if(priority[i]) operator_order[idx++]=expression_operator[i];
        }
        for(int i = 0 ; i < N/2 ; i++){
            if(!priority[i]) operator_order[idx++]=expression_operator[i];
        }
 
        ptr = head_cpy->next;
        idx = 0;
        for(int i = 0 ; i < N/2 ; i++){
            if(priority[i]==1){
                int x = ptr->val;
                int y = ptr->next->val;
                
                if(operator_order[idx]=='+') ptr->val = x+y;
                else if(operator_order[idx]=='-') ptr->val = x-y;
                else if(operator_order[idx]=='*') ptr->val = x*y;
                else ptr->val = x/y;
 
                ptr->next->next->prev = ptr;
                ptr->next = ptr->next->next;
                idx++;
                i++;
            }
            ptr = ptr->next;
        }
 
        ptr = head_cpy->next;
        int sum = ptr->val;
        ptr = ptr->next;
        while(ptr!=tail_cpy){
            int x = sum;
            int y = ptr->val;
            
            if(operator_order[idx]=='+') sum = x+y;
            else if(operator_order[idx]=='-') sum = x-y;
            else if(operator_order[idx]=='*') sum = x*y;
            else sum = x/y;
            idx++;
            ptr = ptr->next;
        }
        if(sum>ans) ans = sum;
        binary++;
    }
    printf("%d\n",ans);
}

 

머리를 안쓰려고 노력하다보니 코드가 길어져버렸다

삼성 코테 b형 대비 겸 linked list도 직접 구현해보았다

비효율적인 코드는 아닌 것 같지만 손가락이 바빴다

연산자 우선순위라든가 중첩된 괄호가 없어서 구현 방법을 생각해내기는 쉬웠지만 구현이 은근 복잡했다

만약 연산자 우선순위랑 중첩 괄호 허용이었으면 못풀었을 것 같다...

 

먼저 수식을 입력 받는데 이 문제가 또 좋았던게 수식에서 숫자는 무조건 한자리 수ㅎㅎ

파싱도 필요 없었다

입력받은 숫자들을 먼저 linked list로 만들고 연산자는 연산자끼리 묶어주었다

 

괄호를 넣는 방법은 게리맨더링 문제처럼 2진수를 이용하였다

+*-*라는 연산자를 받았을 때 예시처럼 * 두개에 괄호가 씌워지면 괄호가 씌워진 연산자, 즉 먼저 계산해주어야 할 연산자를 1이라고 생각했다

예시의 경우는 0101이라는 이진수의 상황이다

 

0000부터 1111까지 이진수를 전부 구해보면 길이가 N인 수식에 괄호를 씌울 수 있는 모든 경우를 구할 수 있다

이 때 1이 두개가 연속 되는 경우는 valid 한 경우가 아니므로 제외해준다

예를 들어 1100은 첫 +와 *에 괄호가 씌워졌다는 말인데

(3+(8)×7)-9×2

이런 케이스는 허용되지 않는다!

 

valid한 경우를 찾았다면 연산자 순서를 다시 만든다

먼저 priority[i]가 1인 경우부터 계산을 해주어야 하니까 1인 경우를 operator_order에 쌓고 그 뒤로 0인 경우를 쌓아주었다

 

다음은 실제 계산 부분!

linked list에서 계산해야 할 위치를 찾으면 그 위치의 값을 계산한 값으로 변경해 준 다음 노드 하나를 삭제해주었다

예시의 상황에서는 8*7을 계산해 56으로 바꾸고 56의 next pointer가 9를 가르키도록 해 준 것이다

 

괄호가 씌워진 우선순위가 1인 부분의 계산이 끝났다면 차례로 나머지 계산들을 해준다

수식의 끝에 도달했다면 정수 하나가 나오는데 그 정수가 최댓값보다 크다면 갱신시켜준다

 

더 깔끔하게 풀 수 있는 방법이 많을 것 같다...