[JS] 올바른 괄호의 개수

DFS를 활용하여 해결하였다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12929

프로그래머스

 

 

처음에는 조합적으로 접근을 해서 '()()()()()' 와같은 형태가 아닌 경우에 각 틈마다 ()를 삽입한 후, set 자료형을 활용해서 중복을 없애는 방식으로 찾아보려 했다.

 

 

function solution(n) {
  const setAry = [...Array(n + 1)].map((_) => new Set());

  setAry[1].add("()");

  for (let i = 2; i <= n; i++) {
    for (const str of setAry[i - 1]) {
      for (let j = 0; j < str.length; j++) {
        const nxStr = str.slice(0, j) + "()" + str.slice(j);
        setAry[i].add(nxStr);
      }
    }
  }

  return setAry[n].size;
}

 

 

직관적인 방식이고 실제로 13번째까지는 정답으로 인정이 잘 된다. 하지만 14번째 이상으로 가면서 시간초과가 발생했다. 너무 많은 경우의 수를 찾기 때문인 것 같다.

 

하지만 생각해보면 괄호란 것은 열거나 닫는 경우의 수밖에 없고 14번째까지만 검사, 즉 2^14 가 dfs의 최대 검색수란게 생각나서 dfs를 활용해서 구현했다.

 

 

괄호를 열거나 닫는 경우의 수를 모두 더해주는데 열린 괄호가 존재하는 경우에만 닫아주는 방식으로 구현하였다.

function solution(n) {
   
    let ret = 0 
    const dfs = (str,l) => {
        
        if(l===n) {
            ret ++
            return
        }
        dfs(str+'(',l+1)
        
        const sCnt = [...str].filter(v => v==='(').length
        const eCnt = [...str].filter(v => v===')').length
        if(sCnt > eCnt) dfs(str+')',l)
    }
    dfs('',0)
    return ret
    
}