[참고] GenerateParentheses - 괄호 생성

APRIL 01, 2021

#. 테스트 문제

  • input n개의 괄호로 나올 수 있는 모든 모양을 출력하는 문제
  • input : 3
  • output : [”((()))”, ”(()())”, ”(())()”, ”()(())”, ”()()()”]

001 01

#. 결과 및 풀이

1. 풀이

@Test
void generatedParentheses() {
    Assertions.assertArrayEquals(new String[]{"((()))", "(()())", "(())()", "()(())", "()()()"}, generatedParentheses_solution(3));
}

String[] generatedParentheses_solution(int n) {
    List<String> result = new ArrayList<>();
    dfs(result, "", n, n);
    return result.stream().toArray(String[]::new);
}

private void dfs(List<String> result, String str, int left, int right) {
    if(left < 0 || left > right)
        return;
    
    if(left == 0 && right == 0) {
        result.add(str.toString());
        return;
    }
    
    dfs(result, str+('('), left-1, right);
    dfs(result, str+(')'), left, right-1);
}

배웠다

  • input과 output의 배열 길이가 동일하면 미리 공간을 만들어 놓자!
  • input을 활용할 수 있는지 확인하자! (stack에 index만 들어가는 것처럼)

작업 기록 블로그