Remove Invalid Parentheses

Remove Invalid Parentheses

문제 내용

'(' 와 ')' 로 구성된 문자열이 있다.

해당 문자열을 중괄호라고 부를때 '(' 와 ')'의 pair가 맞게 할 수 있는 최소한의 delete가 된 가능한 모든 문자열을 결과로 return 해라

단, 중간에 문자가 있을 수 있다.

 

접근 방법

일반적인 Parentheses 문제를 이용해서 문제를 해결해 나가야 한다.

우선 validation check에 대해서 생각해 보자.

기본적으로 Parentheses 문제는 '('의 갯수가 무조건 ')'의 갯수보다 많은 경우 Validation이 된다고 생각해야한다.

2020.09.15 - [Problem Solving] - 괄호 변환

문제에서 getBalancedCount 부분을 참고하자. 

이 내용을 기본으로 해서 다음과 같이 2가지 방법으로 접근할 수 있다.

• Full search
• Backtracking

 

Full Search

가장 쉽게 접근 가능한 방법이다.

이럼 문제가 있을 경우 답은 아래 2가지가 가능하다.

가장 간단한 방법은 왼쪽 부터 오른쪽으로 모든 경우의 수를 대입하는 방법이다.

즉 N개의 값을 모두 하나씩 빼보고, 이후에 2번째것을 다시빼보고, 다음에 3번째 것을 빼보고 하면서 DFS처리를 한다.

물론 Validation이 되는 순간 바로 종료 처리 하고 특정 depth이상은 DFS 처리를 안하는 방법도 있겠지만,

최악의 경우를 생각한 Time Complexity는

$$ O(N^N) $$

이 된다. 

첫번째 loop로 N 회를 돌것이고 이 N회에 곱하기 N-1회를 다시 돌것이고 이것이 0까지 될때까지 회전함으로 $ N^N $ 이된다.

 

Backtracking

상기 방법의 문제는 한번 사용 된 값이 다시 사용 될 수 있다는데 있다.

이 부분을 최적화 하기위해서 한번 나온 index의 값은 단 한번만 사용되게 만들어야 한다.

여기 index가 0인 char가 있다. '(' 이 index 0은 다음과 같이 2가지의 선택권이 주어진다.

사용되거나 사용되지 않거나이다.

이를 이용하면 N 개의 Array는 한번에 2가지씩 선택권을 갖음으로 $ 2^N $ 으로 Time Complexity를 줄일 수 있다.

위의 그림을 보면 좀더 명확한데 index 0의 '('는 삭제되거나 남거나 2가지의 선택을 하고 다시 재활용 되지 않는다.

이것을 한단계 더 내려가면 아래와 같다.

이런식으로 index를 하나씩 늘려가다 보면 결국 index의 위치는 주어진 문제 string의 길이와 같아지게 된다.

이때 left의 출현 횟수와 right의 출현 횟수가 같다면 해당 문자열은 정답이라고 볼 수 있다.

이때 주의 해야할 것은

• left count <= right count 를 유지 시켜줘야 한다

그래서

상기 그림의 남기기는 발생하면 안된다. 최종적으로 count가 같아 지더라도 invalid된 결과이기 때문이다.

여기서 몇가지를 더 filtering 처리 할 수 있는데, Time complexity를 보면 $$ O(2^N) $$ 임으로 더 다루지 않겠다.

답은 아래와 같다.

var removeInvalidParentheses = function(s) {
    let minRemove = Number.MAX_SAFE_INTEGER;
    let set = new Set();

    dfs(0, 0, 0, 0, '');

    return [...set];

    function dfs(index, leftCount, rightCount, removeCount, str) {
        let char = s.charAt(index);

        //finish state
        if (index === s.length ) {
            if(leftCount === rightCount && removeCount <= minRemove){
                if (removeCount === minRemove) {
                    set.add(str);
                } else {
                    minRemove = removeCount;
                    set.clear();
                    set.add(str);
                }
            }
            return;
        }


        //discard condition
        if (char === '(' || char === ')') {
            dfs(index + 1, leftCount, rightCount, removeCount + 1, str);
        }

        str += char;

        //continue condition
        if (char !== '(' && char !== ')') { //일반 글자일 경우
            dfs(index + 1, leftCount, rightCount, removeCount, str);
        } else if(char === '('){ //왼쪽 일경우
            dfs(index + 1, leftCount+1, rightCount, removeCount, str);
        } else if (char === ')' && rightCount < leftCount) { //오른쪽이고 left가 오른쪽보다 클경우, 그외의 경우는 모두 fail
            dfs(index + 1, leftCount, rightCount+1, removeCount, str);
        }

        str.substring(str.length - 2, str.length -1);
    }
};