.leetcode(22. Generate Parentheses)

문제

leetcode.com/problems/generate-parentheses/

Generate Parentheses - LeetCode

문제 풀기 전

1. stack이 필요할거같았다.
2. 전역변수를 쓰면 편할거 같았다.
3. end조건만 챙기고 다 돌면 풀 수 있겠다라는 생각이 들었다.
4. 요소가 2개로 한정되어있어서 재귀를 쓸때 2번호출하는걸 로직에 넣으면 해결되겠다는 생각도 하였다.

직접 푼 풀이

class Solution {
    private List<String> returnList = new ArrayList<>(); 
    private int[] parentheses;
    private int n;
    public List<String> generateParenthesis(int n) {
        this.n = n;
        parentheses = new int[n*2];
        file(n,n, 0);

        return returnList;
    }

    private void file(int left, int right, int index) {
        if (left > right) {
            return;
        }

        if (index == n*2) {
            returnList.add(makeString(parentheses));
            return;
        }

        if (left > 0) {
            parentheses[index] = 1;
            file(left-1, right, index+1);
            parentheses[index] = 0;
        }

        if (right > 0) {
            parentheses[index] = 2;
            file(left, right-1, index+1);
            parentheses[index] = 0;
        }
    }

    private String makeString(int[] parentheses) {
        StringBuilder builder = new StringBuilder();
        for(int each: parentheses) {
            builder.append(each == 1 ? "(" : ")");
        }

        return builder.toString();
    }
}

느낀점

1. 전역변수를 쓰는게 확실히 좋다. 필요시 로컬 변수로 변환해주면 되겠다는 생각이 들었다.
2. 요소의 갯수로 로직을 유추하는건 아주 좋았다.
3. 이런 문제는 결국 마지막형태를 저장/출력하는 형식이므로, 이렇게 끝까지 가는 경우는 전체String + pos 인수조합으로 넘기는것도 효과적이라는 생각이 들었다.
4. 문제를 풀기전에 경우의 수가 얼마나 나올지 계산해보는 습관이 필요하다고 생각이 들었다. 이번에는 2^2n이 중복을 모두 합쳤을때 생겼고 실제로 수학적으로는 아마 (2n)! /n! * n!가 되었을것이다. 그리고 주어진 제한에 의하면 8까지만 하기때문에 최대 16!/8!/8!=12870 정도만 세면 최대의 경우의 수를 알 수 있고 2^10은 그렇게 큰 수가 아니기때문에 이건 Brute Force(무차별)로 풀 수 있다는 논리까지 끌어냈어야 진정한 답으로 인정할 수 있었을 것이다.
5. 실제로 내가 푼 방법은 BackTracking이었다. Brute Force는 모든 경우의 수를 한 후에 valid과정을 통해 정답만 추려낸다고 하면 나는 가능한 경우만 먼저 추려낸 경우의 수를 찾아내는 원리다. 여기서 적용한건 (괄호보다 )괄호의 수가 많으면 안된다고 생각했다. 백트래킹은 조건을 만족하는 것만 찾아내는걸 얘기하는데 습관적으로 그렇게 접근한 거 같다.
6. Closure Number라는 방법도 있는데 아주 재미난다. 이 방법은 탑다운 개념으로 크게 블록을 잡아 사고하여 푸는 방식이다. 개념에 대해서는 수학적인 부분이라 설명을 찾아보기 어려운데, 이렇게도 풀 수 있구나 라는 걸 보여준다.

누적되는 알고리즘 접근 설명서

1. 제한값이 있다면 최대의 경우의 수로 계산하고 최대 시간복잡도를 유추할 수 있을지 습관을 들여본다.
2. 전역변수를 과감히 도입한다.
3. Brute Force, Back Tracking 이 두 방법을 고려해본다.