LeetCode: 22번 (Generate Parentheses) [JAVA]

문제 링크

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

Generate Parentheses - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 숫자 n에 대하여 만들 수 있는 조합을 만드는 함수를 재귀호출을 바탕으로 작성
   • 현재 구성 상 양쪽 괄호 쌍의 개수가 동일하다면 다음에는 무조건 왼쪽 괄호만 추가
   • 왼쪽 괄호가 더 많다면 왼쪽 괄호를 추가하거나 오른쪽 괄호를 추가
   • 왼쪽 괄호를 모두 채웠다면 단순 오른쪽 괄호만을 추가
2. 그리고 결과를 바탕으로 괄호쌍 String을 생성하는 함수를 작성하여 결과 리스트에 추가후 반환

 개수에 맞는 가능한 괄호 쌍 조합을 만들어서 반환해야 하는데, 단순 조합이 아니라 괄호의 쌍이 올바르게(오른쪽 괄호가 있다면 무조건 이에 맞는 왼쪽괄호가 왼쪽에 존재해야 함) 조합이 만들어져야 하기에 해당 부분에 대한 함수를 직접 작성해야 한다.

 우선 재귀호출을 기반으로 함수를 작성한다. 전체 괄호의 순서를 담을 int 배열을 바탕으로 -1을 왼쪽 괄호, 1을 오른쪽 괄호로 정하고 해당 배열을 채워나가는 형태로 작성하며, 기저조건은 해당 배열을 모두 채울 때를 바탕으로 한다. 그리고 주어질 수 있는 전체 케이스 3종류에 대해 다음 함수를 작성하는 데, 우선 여태까지의 왼쪽과 오른쪽 괄호 개수가 동일하다면 무조건 왼쪽 괄호를 추가하고 다음 함수를 호출, 왼쪽 괄호가 더 많은 상황이라면 왼쪽 괄호를 추가하거나 오른쪽 괄호를 추가하고 다음 함수를 호출하고, 마지막으로 왼쪽 괄호의 개수가 n과 동일하다면 오른쪽 괄호만 추가하고 함수를 호출한다.

 그리고 기저조건에 도달할 시 채운 int 배열을 바탕으로 String 타입의 괄호 쌍을 생성하는 함수를 작성하여, 결과 String을 생성 후 답을 채울 ArrayList에 추가하고, 결과적으로 해당 ArrayList를 반환한다.

 

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

    public List<String> generateParenthesis(int n) {
        int[] array = new int[2 * n];
        generateComb(n, 0, 0, 0, array);
        return ans;
    }

    void generateComb(int n, int now, int leftCount, int rightCount, int[] array) {
        if (now == n * 2) {
            generatePair(array);
            return;
        }

        if (leftCount == rightCount) {//현재 양쪽 괄호 쌍이 동일하다면
            array[now] = -1;
            generateComb(n, now + 1, leftCount + 1, rightCount, array);
        } else if (leftCount < n) {//왼쪽 괄호에 추가 여유가 있다면
            array[now] = -1;
            generateComb(n, now + 1, leftCount + 1, rightCount, array);
            array[now] = 1;
            generateComb(n, now + 1, leftCount, rightCount + 1, array);
        } else if (leftCount == n) {//왼쪽 괄호를 모두 채웠다면
            array[now] = 1;
            generateComb(n, now + 1, leftCount, rightCount + 1, array);
        }
    }

    void generatePair(int[] array) {//결과 String 생성
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < array.length; i++) {
            if (array[i] == -1) {
                sb.append('(');
            } else {
                sb.append(')');
            }
        }

        ans.add(sb.toString());
    }
}

결과