[Leet Code] Generate Parentheses

안녕하세요! 오늘은 6월 첫째주 2번째 알고리즘인 Generate Parentheses 풀이를 작성해보겠습니다.

---

문제

요약
Input으로 주어지는 n 개의 괄호가 포함된 string 들을 List 형태로 return 하는 문제입니다.

처음으로 생각한 방법

String 배열에 ( 와 ) 를 n 만큼 저장해놓은 후, 배열 내에서 괄호의 순서를 바꿔가면서 유효한지 check 하는 방법을 생각했습니다.

하지만, 구현이 너무 어려워서 다른 방법을 생각해냈어요.

두번째로 생각한 방법

재귀 함수를 활용하는 방법입니다. 함수의 인자로 주어지는 string 에 ( 또는 ) 를 추가하여 그것이 유효한지 확인해 result 리스트에 추가합니다.
결과는 Accept!

이제 코드 설명에 들어가겠습니다.

---

코드 설명

ArrayList<String> result = new ArrayList<>();

Solution 클래스의 전역 변수로 result 리스트를 선언해줍니다.

makeParenthesis("", n, 0);

솔루션 함수인 generateParenthesis 함수에는 위처럼 재귀 함수를 호출해줍니다.

private void makeParenthesis(String s, int n, int check) {
    if (check < 0 || check > n) return;
    if (s.length() == n * 2) {
        if (check == 0) result.add(s);
        return;
    }

    makeParenthesis(s + "(", n, check + 1);
    makeParenthesis(s + ")", n, check - 1);
}

재귀함수입니다.

check 라는 변수는 ( 일 때 +1, ) 일 때 -1이 되는 변수입니다.
이 check 변수가 음수라면 유효하지 않은 괄호가 포함된 문자열이 됩니다.
check 변수가 n 보다 크다면, ( 가 n 이상인 문자열이므로 유효하지 않습니다.

s 의 길이가 n * 2 라면 유효한 문자열인지 확인이 필요합니다.
만약 check 변수가 0이라면 완전한 괄호만 존재하는 정답 문자열이므로 result 리스트에 추가합니다.
그것이 아니라면 아무런 처리도 하지 않고 return 합니다.

위의 경우가 모두 아니라면 s 에 괄호를 추가해도 되는 경우이기 때문에 순서대로 함수를 재귀호출하면서 ( 또는 ) 를 s 에 더해 함수에 전달합니다.

전체 코드

class Solution {
    ArrayList<String> result = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        makeParenthesis("", n, 0);

        return result;
    }

    private void makeParenthesis(String s, int n, int check) {
        if (check < 0 || check > n) return;
        if (s.length() == n * 2) {
            if (check == 0) result.add(s);
            return;
        }

        makeParenthesis(s + "(", n, check + 1);
        makeParenthesis(s + ")", n, check - 1);
    }
}

---

마무리

재귀 호출로 괄호를 푸는 방법을 조언을 받아서 풀어봤습니다..ㅎ.ㅎ
이번 포스팅도 읽어주셔서 감사합니다 :)