릿코드 - 22. Generate Parentheses(자바)

릿코드 - 백트래킹 주제의 문제를 풀다가 아직도 갈 길이 멀었구나.. 라는 것을 느끼며 배운 것을 정리해보고자 합니다.

​

1. 문제 설명

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1

Output: ["()"]

Constraints:

1 <= n <= 8

​

** 이 문제는 숫자 n이 주어지면 n 개의 짝이 맞는 괄호 패턴을 찾아내서 리턴해주면 되는 것이였습니다.

​

2. 문제 풀이

해당 문제를 풀기 위해서는 하기의 규칙을 찾아내서 구현해야 했습니다.

')' (닫는 괄호)는 항상 '(' (여는 괄호) 다음에 더한다.

1번을 하기 위해 open , close 라는 변수로 '(' , ')' 의 수를 확인

만약 여는 괄호가 주어진 숫자 n보다 작다면 여는 괄호를 더해줄 수 있다.

닫는 괄호가 여는 괄호보다 적다면 닫는 괄호를 더해줄 수 있다.

​

저는 상기의 4가지를 생각하지 않고.. 무지성으로 모든 상황을 뽑아서 패턴이 맞는 것만 찾아서 반환하도록 했었는데 n이 4일때부터 바로 시간초과 오류가 나오더라구요.. ㅠ

​

3 코드 )

public static void main(String[] args) {
    int n = 3;
    System.out.println("generateParenthesis(n) = " + generateParenthesis(n));
}
static int N;
static List<String> result;
public static List<String> generateParenthesis(int n) {
    N = n;
    result = new ArrayList<>();
    backtracking(0,0,"");
    return result;
}

public static void backtracking(int open, int close, String s){

    if(s.length() == N*2){
        result.add(s);
        return;
    }

    if(open < N){
        backtracking(open + 1 , close , s + "(");
    }

    if(close < open) {
        backtracking(open , close+1 , s + ")");
    }
}