[Leet Code] Generate Parentheses

기면지·2021년 6월 16일
0

LeetCode

목록 보기
19/20
post-thumbnail

안녕하세요! 오늘은 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);
    }
}

마무리

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

profile
𝙎𝙈𝘼𝙇𝙇 𝙎𝙏𝙀𝙋𝙎 𝙀𝙑𝙀𝙍𝙔 𝘿𝘼𝙔

0개의 댓글