꿀잠

https://leetcode.com/problems/generate-parentheses/description/

주어진 n의 개수에 따라 열고 닫히는 괄호를 만드는 문제이다. 괄호는 Stack 자료구조 문제 관련해서 자주 등장하는 알고리즘 문제이다. 괄호를 여는 부분이 먼저 나오고 닫히는 부분이 뒤에 나오기 때문에 스택에 저장하고 꺼낼 때 괄호를 완성해 줄 수 있기 때문이다.

하지만 해당 문제는 소괄호 하나만 등장하기 때문에 스택을 특별히 사용할 필요는 없었다. 문자열을 만들면서 열려있는 괄호가 닫히는 괄호가 생성되기 전에 충분히 있는지, 그리고 최종적으로 완성된 문자열의 경우 열고 닫히는 괄호의 숫자가 알맞게 있는지 체크해주면 되었다. 문자열을 생성하는 과정은 백트래킹 형태의 dfs를 이용해 주었고, 효율을 높이기 위해 괄호가 완성되는 형태를 가질 수 없는 경우를 필터링 해주었다. 아래는 통과한 코드이다.

public class Solution {  
  
    static String[] letter = {"(", ")"};  
  
    public List<String> generateParenthesis(int n) {  
        List<String> answer = new ArrayList<>();  
        StringBuilder sb = new StringBuilder();  
        sb.append("(");  
        dfs(n * 2, sb, answer);  
  
        return answer;  
    }  
  
    private void dfs(int n, StringBuilder sb, List<String> answer){  
        boolean isLast = n == sb.length();  
        if(!isPossible(sb.toString(), isLast)){  
            return;  
        }  
  
        if(isLast){  
            answer.add(sb.toString());  
            return;  
        }  
  
        for(int i = 0; i < 2; i++){  
            sb.append(letter[i]);  
            dfs(n, sb, answer);  
            sb.deleteCharAt(sb.length() - 1);  
        }  
    }  
  
    private boolean isPossible(String str, boolean isComplete){  
        int check = 0;  
        for(char c: str.toCharArray()){  
            if(c == '('){  
                check++;  
            }else{  
                if(check == 0){  
                    return false;  
                }  
  
                check--;  
            }  
        }  
  
        return isComplete ? check == 0 : true;  
    }  
  
}

괄호를 체크하기 위해 문자열을 char 배열로 변환해서 해주었는데, 다른 코드들을 참고하니 재귀를 돌면서 left와 right 개수를 단순 int 값으로 처리해서 확인하는 방법이 속도가 좋아서 다음에 괄호 관련된 문제 풀이 시 참고할 방법을 얻을 수 있었다.