baekjoon. 괄호 제거

문제

링크

풀이

조합과 스택을 이용하는 문제

괄호의 쌍이 최대 10개이기 때문에 조합을 사용해도 시간 초과가 되지않는다

우선 문자열에 존재하는 괄호쌍의 인덱스 두 가지를 묶어서 저장한다

(0/(0))의 경우

(0,6), (3,5) 두 쌍의 괄호가 나오는데 이 괄호의 수만큼 조합을 구한다

아무것도 고르지 않을 때, (0,6)만 고를 때, (3,5)만 고를 때, (0,6), (3,5) 두 가지를 고를 때

조합 4가지를 구했으면 이에 조합 가지 수에 맞추어서 괄호를 삭제해주면된다

아무것도 고르지 않았을 때는 처음 문자열과 같으니 생략

(0,6)

0/(0)

(3,5)

(0/0)

(0,6), (3,5)

0/0

구해서 출력해주면된다

코드

    function getPSIndex(string) {
        const arr = string.split('');
        const stack = [];
        const index = [];
        for(let i=0; i<arr.length;i++){
            if(arr[i] ===')'){
                for(let j=stack.length-1;j>=0;j--){
                    if(stack[j]==='(') {
                        index.push([i,j]);
                        stack[i] = '*';
                        stack[j] = '*';
                        break;
                    }
                }
                continue;
            }
            stack.push(arr[i]);
        }
        return index;
    }

    function getSet(arr){
        const k = 1<<arr.length;
        const set = [];
        for(let i=1; i<k;i++){
            const temp = [];
            for(let j=0; j<arr.length;j++){
                if(i&(1<<j)){
                    temp.push(arr[j]);
                }
            }
            set.push(temp);
        }
        return set;
    }

    function solution(input){
        const indexArr = getPSIndex(input);
        const set = getSet(indexArr);

        const removeDup = new Set(set.map(v=>{
            const arr = input.split('');
            const temp = v.flatMap(v=>v).sort((a, b) => b-a);

            temp.forEach(v=>arr.splice(v,1));
            return arr.join('');
        }));

        const answer = Array.from(removeDup);
        console.log(answer.sort((a, b) => a<b ? -1:1).join('\n'));
    }