Portfolio

📄문제

✏️풀이

재영

저는 이걸 봤을 때... 이게 DP인가 싶기는 했지만... 일단 DP로 풀어봤읍니다!

(아, 문제가 DP가 아니라고 말하는 게 아니라, 제가 푼 방법이 명확한 DP인지가 헷갈렸네유😅)

이 문제를 봤을 때, 최대한 분할해서 접근하려 생각해보았어요.

괄호의 값을 저장할 Array를 생성한다.

이때 저는, n의 값과 일치한 인덱스의 값을 반환하기 위해, length를 +1 해주었읍니다.

[[0][1][2][3][4][5][6][7][8]] ⇒ 9 → arr (최종결과값)


return arr[n]

그럼, 이제 돌려봅시다.

괄호를 채울 때가 언제일까요? 만약 1개 → 2개를 만든다고 생각해봅시다.

그럼 다음 2가지일 것입니다. ()()와, (())겠죠?

그렇다면, 여기서 일단 한 가지 규칙을 도출할 수 있어요.

💡

핵심 1. 만약 괄호를 넣는다고 친다면, 적어도 일단 (을 발견한다면 왼쪽에 괄호를 하나 넣고, 그 오른쪽에 괄호를 넣는다.

그런데, 여기서 증명되지 않은 하나가 있어요. '바로 )의 오른쪽에도 ()를 넣어야 하느냐' 입니다. 현재는 오른쪽에서 넣지 않아도 이미 중복된 결과가 나왔기 때문이죠. 그렇다면, 이 역시 반드시 필요한 연산인지 점검할 필요가 있었어요.

그렇다면 우리의 핵심 2번째는 다음 가설에 대한 검증일 거에요.

💡

핵심 2. 만약 )의 오른쪽에 괄호를 넣지 않아도, 이 점화식은 전체의 해를 충족한다.

그렇다면 문제에서 주어진 해에 적용해봅시다.

["((()))", "(()())", "(())()", "()(())", "()()()" ]

여기서 , )를 고려하지 않은 연산 결과가 이 모든 것을 다 충족시킨다면, 결과적으로 )에 대한 추가적인 연산이 필요 없겠죠?

먼저 n-1인 괄호 2개를 사용하여 만들어낸 (()) 를 적용한다면 다음 3가지 결과가 나옵니다.

💡

()(()) (()()) (()()) ((()))

그렇다면, ()()에서 적용하면, 어떻게 될까요?

💡

()()() (())() ()()() ()(())

따라서, 이에 대한 중복된 결과를 제하면, 결과적으로 모든 해를 도출할 수 있음을 증명했습니다.

코드

이를 코드로 정하면 다음과 같겠군요!

메인 함수 generateParenthesis

먼저 for문을 돌리면서, 1~n까지의 케이스의 괄호들을 만들어줍니다.

이때 나온 애들은 결과적으로 중복된 것들이 있으므로, i가 끝나기 전에 Set으로 없애주면서 처리해줍니다.


const generateParenthesis = n => {
  const arr = Array.from({ length: 9 }, () => []) // 결과값을 담는 DP Array
  for (let i = 1; i < n + 1; i += 1) { // 결과값을 하나하나 담기위한 for
    if (i === 1) {
      arr[i].push('()');
      continue;
    }
    let nowResult = []; // 지금까지의 맞는 괄호들을 다 넣어줄 거다.
    arr[i - 1].forEach(brackets => { // i - 1번째에 있는(이전 저장된 배열들을 순회하면서 나온 괄호)
      for (let j = 0; j < brackets.length; j += 1) { // 쭉 순회하다가
        if (brackets[j] === '(') {
          nowResult.push(pushedParenthesis(brackets, j))
          nowResult.push(pushedParenthesis(brackets, j - 1))
        }
      }
    })
    arr[i] = [...new Set(nowResult)] // 중복된 것들은 다 생략해줄 것. -> i번째에 있는 올바른 괄호들의 배열들
  }
  return arr[n]
}

서브 함수 pushedParenthesis

얘는 괄호를 다 넣어주는 역할을 해줍니다.


const pushedParenthesis = (brackets, idx) => {
  return brackets.slice(0, idx + 1) + '()' + brackets.slice(idx + 1, brackets.length)
}

결과

결과적으로... 아슬아슬하게 통과하기는 하네유...! (102ms, faster than 38%)


const generateParenthesis = n => {
  const arr = Array.from({ length: 9 }, () => [])
  for (let i = 1; i < n + 1; i += 1) {
    if (i === 1) {
      arr[i].push('()');
      continue;
    }
    let nowResult = [];
    arr[i - 1].forEach(brackets => {
			const len = brackets.length;
      for (let j = 0; j < len; j += 1) {
        if (brackets[j] === '(') {
          nowResult.push(pushedParenthesis(brackets, j)) // ()
          nowResult.push(pushedParenthesis(brackets, j - 1))
        }
      }
    })
    arr[i] = [...new Set(nowResult)]
  }
  return arr[n]
}

const pushedParenthesis = (brackets, idx) => {
  return brackets.slice(0, idx + 1) + '()' + brackets.slice(idx + 1, brackets.length)
}

효성


var generateParenthesis = function(n) {
    const st = ['(']; 
    let openCnt = 1;
    const LEN = n*2
    const parenthesis = [];

    function dfs() {
        if(openCnt < 0 || st.length > LEN) {
            return;
        }
        if(openCnt === 0 && st.length === LEN) {
            parenthesis.push(st.join(""));
            return;
        }
        st.push('(');
        openCnt++;
        dfs();
        st.pop();
        openCnt--;

        st.push(')');
        openCnt--;
        dfs();
        st.pop();
        openCnt++;
    }
    
    dfs();
    return parenthesis;
}

은찬


const dfs = (n, left, right, string, answer) => {
    if(left > n || right > n){
        return;
    } else if(left === n && right === n){
        answer.add(string);
        return;
    }
    
    dfs(n, left + 1, right, string + "(", answer);
    dfs(n, left + 1, right, "(" + string, answer);
    
    if(right < left){
        dfs(n, left, right + 1, string + ")", answer);
    }
}

const generateParenthesis = (n) => {
    const answer = new Set();
    
    dfs(n, 1, 0, "(", answer);
    
    return [...answer];
};

Generate Parentheses

📄문제

✏️풀이

코드

결과