평가

리트코드를 사용하면서 중간 중간 점검을 안하는데, 꼭 해주자.
IDE 없으면 디버깅하기 힘들다.

괄호 문제가 나오면 스택을 떠올리자. 이번 문제 역시 스택(재귀) 개념으로 푸는 문제

문제 링크 : https://leetcode.com/problems/generate-parentheses/

결과 : 성공
풀이시간 :50분
다만 시/공간 복잡도가 매우 낮게 나옴
맞았지만, 일반적인 방식으로 푼 게 아니라 오답노트를 작성하려 함

내 풀이(Bad)

아이디어

3쌍의 괄호를 사용해 만들 수 있는 경우의 수는 다음과 같습니다.

3쌍으로 만드는 완전한 묶음
(()())
((()))
2쌍 묶음 + 1쌍 묶음
(()) ()
()() ()

1쌍 완전한 묶음 + 2쌍 묶음
() (())
    

n쌍으로 만든다고 하면

• n쌍으로 만드는 완전한 묶음,
• n-1 쌍 & 1쌍 묶음의 조합
• n-2 쌍 & 2쌍 묶음의 조합
• ...
• 1쌍 & n-1 쌍 묶음의 조합

위 경우들을 계산한 뒤 Set 에 담아 중복을 제거하자는 아이디어입니다.
풀이에서 사짜 느낌 납니다. 풀면서도 다른 풀이가 있을거라 예상했습니다. 다만, n의 범위가 8까지라 충분히 풀 수는 있겠다 생각했습니다.

코드는 아래와 같습니다.

class Solution {

    public List<String> generateParenthesis(int n) {
        Map<Integer, Set<String>> cases = new HashMap<>();

        for(int i=1; i<=8; i++){
            add(i, cases);
        }
        Set<String> answers = cases.get(n);
        return answers.stream().collect(Collectors.toList());
    }

    public void add(int level, Map<Integer, Set<String>> cases) {
        Set<String> result = new HashSet<>();

        if (level == 1) {
            result.add("()");
            cases.put(level, result);
            return;
        }

        // n쌍을 이용해서 하나의 chunk를 만드는 코드
  		// n-1쌍으로 만들 수 있는 경우의 수를 모두 찾아,
	    // 각각의 경우를 () 로 감싸줬습니다.
        Set<String> x = cases.get(level - 1);
        for(String each: x) {
            String newEach = "(" + each + ")";
            result.add(newEach);
        }

		// 두 개의 chunk로 나누어 경우의 수를 찾습니다
        for(int i=1; i<level; i++) {
            // i랑 level - i로 나눠 각각의 쌍을 조합합니다.
            Set<String> first = cases.get(i);
            Set<String> second = cases.get(level - i);

            for(String eachFirst: first) {
                for(String eachSecond: second) {
                    result.add(eachFirst + eachSecond);
                }
            }
        }
        
        cases.put(level, result);
    }
    
}

더 좋은 풀이

더 좋은 풀이가 있어 아이디어를 참고 후 다시 풀었습니다.

아이디어

아이디어는 "( 의 개수는 항상 )보다 많거나 같아야 한다" 입니다.
몇 가지 예시를 적어보면 이해가 되실 겁니다.

풀이는 다음과 같습니다.
먼저 문자열에 (를 넣습니다.
남아있는 ( 개수 = n-1, ) 개수 = n 개를 넣고 재귀함수 make를 실행합니다.
균형잡힌 괄호를 넣기 위해서는 둘 중 한 가지 조건을 만족해야 합니다.

1. (가 남아 있는 경우, ( 를 넣을 수 있습니다.
2. (개수 < ) 개수면 )를 넣을 수 있습니다.
   

코드는 아래와 같습니다.

  import java.util.*;

class Solution {
    static List<String> answers;

    public List<String> generateParenthesis(int n) {
        answers = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        sb.append('(');
        make(sb, n - 1, n);

        return answers;
    }    

    // openCnt: 사용가능한 남아있는 ( 개수
    // closeCnt: 사용가능한 남아있는 ) 개수
    public void make(StringBuilder sb, int openCnt, int closeCnt) {
        if (openCnt == 0 && closeCnt == 0) {
            answers.add(sb.toString());
            return;
        }
        // 열림 괄호를 넣는다
        if (openCnt != 0) {
            sb.append('(');
            make(sb, openCnt - 1, closeCnt);
            sb.deleteCharAt(sb.length() - 1);
        }

        if (openCnt < closeCnt) {
            sb.append(')');
            make(sb, openCnt, closeCnt - 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

결과