2800_괄호 제거

Concept & Idea

메모리 초과로 인해서 고생했다..
맨처음에 생각을 좀 잘못해서, dfs 인자로 stack과 스트링을 넘겼기 때문..
최대 스트링이 200인데, DFS 로 풀었을 때, 2^200개의 노드가 생기기 때문에 그렇게 풀면 안된다.

+ Match 를 기록하는 함수 역시 For 문으로 앞뒤에서 체크하는걸로 구현했는데,, () + () 이러한 수식의 경우, 잘못 체크될 수 있기 때문에 아래와 같이 stack으로 푸는것으로 변경하였다. (괄호하면 스택인듯..)

DFS 인자에는 현재의 Index만 넘기고, 해당 함수내에서 넣기로 선택한 ()의 경우, choice를 True로 하고
) 인 경우, 이전 매칭되는 녀석이 들어왔을 때에만 선택되도록 해줘야한다.

 

Code

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <set>
#define all(v) (result).begin(), (result).end()
using namespace std;
string input;
int record_match[201];
bool choices[201];
vector<string> result;
void dfs(int index){
    if(index == input.size()) {
        string rs = "";
        for(int i=0; input[i]; i++) {
            if((input[i] == '(' || input[i] == ')') && !choices[i]) {
                continue;
            }
            rs+=input[i];
        }
        if (rs != input)
            result.push_back(rs);
        return;
    }
    if(input[index] == '(') {
        dfs(index+1);
        choices[index] = true;
        dfs(index+1);
        choices[index] = false;
        
    } else if (input[index] == ')' && choices[record_match[index]]) {
        choices[index] = true;
        dfs(index+1);
        choices[index] = false;
    }else dfs(index+1);
    
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>input;
    
    stack<int> st;
    for(int i=0; input[i]; i++) {
        if(input[i] == '(') st.push(i);
        if(input[i] ==')') {
            record_match[i] = st.top();
            record_match[st.top()] = i;
            st.pop();
        }
    }
    dfs(0);
    sort(all(result));
    result.erase(unique(all(result)), result.end());
    for(auto& it : result)
        cout<<it<<'\n';
    
}

 

Fealing

항상 느끼는 거지만, 얼추 보면 풀이가 맞는데 틀렸을 경우에 요래조래 바꿔가며 고생하는 것보다
그냥 처음부터 다시 짜는게 생각 정리도 잘되고, 속도도 빠른 것 같다

내 코드가 깔끔하지 않았기 때문일까.. 그냥 이전 코드는 잘못된 흐름을 표현하고 있기 때문인걸까.