99클럽 코테 스터디 18일자 TIL + count-sorted-vowel-strings

이월(0216tw)·2024년 6월 6일

99클럽 TIL 개발자 취업 기능개발 동적계획법 미들러 자바 코딩테스트 코딩테스트준비 항해99

99클럽/알고리즘풀이

목록 보기

20/38

문제 출처

https://leetcode.com/problems/all-possible-full-binary-trees/(리트코드)

학습 키워드

동적계획법

시도 방법

혼자서 풀지 못해서 GPT 기반으로 도움을 받아 작성하려고 한다.

내 GPT 가 작성한 코드


class Solution {
    
    private Map<Integer, List<TreeNode>> memo = new HashMap<>();
        
    public List<TreeNode> allPossibleFBT(int n) {
            
        if(n % 2 == 0) return new ArrayList<TreeNode>(); //짝수일 경우 빈 리스트 반환 

        if (memo.containsKey(n)) return memo.get(n);

        List<TreeNode> result = new ArrayList<>(); 

        if(n==1) {
            result.add(new TreeNode(0)); //n 이 1이면 단일노드
        } else {
            for (int leftCount = 1; leftCount < n; leftCount += 2) {
                int rightCount = n - 1 - leftCount;
                List<TreeNode> leftTrees = allPossibleFBT(leftCount);
                List<TreeNode> rightTrees = allPossibleFBT(rightCount);
                for (TreeNode left : leftTrees) {
                    for (TreeNode right : rightTrees) {
                        TreeNode root = new TreeNode(0);
                        root.left = left;
                        root.right = right;
                        result.add(root);
                    }
                }
            }
        }

        memo.put(n , result);
        return result ;
    }
}

코드설명

일단 완전이진트리이기때문에 노드의 자식이 0개 혹은 2개이다.

n = 1 일때는 노드가 하나밖에 없으므로 단일 노드 하나만 반환하면 된다

n = 3 일때는 하나의 케이스만 나온다. [0 , 0 , 0 ] (여기서 0은 노드가 있는 케이스이다)

n = 5 일때부터 규칙을 찾아야하는데 이부분에서 막혔다.

GPT가 알려주는 재귀적 분할

n=5일때 )
leftCount = 1 이면 오른쪽이 3개가 달려있다는 의미이다.
rightCount = 1 이면 왼쪽에 3개가 달려있다는 의미이다.

leftCount 일 경우 왼쪽 트리는 1개 이므로 [0] 이다. 오른쪽 트리는 3이므로 각 자식인
leftCount 가 [0] , rightCount 가 [0] 을 가진다. 이를 결합해 [0,0,0]이 생성된다.

재귀적인 접근을 통해 가능한 왼쪽과 오른쪽 서브트리를 결합한다.

그리고 중복된 계산을 피하기 위해 메모이제이션 기법을 이용한다.

소스분석

```java

class Solution {
    
    private Map<Integer, List<TreeNode>> memo = new HashMap<>();
        
    public List<TreeNode> allPossibleFBT(int n) {
            
        if(n % 2 == 0) return new ArrayList<TreeNode>(); 

        if (memo.containsKey(n)) return memo.get(n);


        List<TreeNode> result = new ArrayList<>(); 

        if(n==1) {
            result.add(new TreeNode(0)); //n 이 1이면 단일노드
        } else {
        
        
        
            for (int leftCount = 1; leftCount < n; leftCount += 2) {
                int rightCount = n - 1 - leftCount;
                List<TreeNode> leftTrees = allPossibleFBT(leftCount);
                List<TreeNode> rightTrees = allPossibleFBT(rightCount);
                for (TreeNode left : leftTrees) {
                    for (TreeNode right : rightTrees) {
                        TreeNode root = new TreeNode(0);
                        root.left = left;
                        root.right = right;
                        result.add(root);
                    }
                }
            }
            
            leftCount가 1 , 3 , 5 ... n까지 진행된다. 
            자연스럽게 rightCount는 leftCount를 뺀 값이 된다. 
            
            그리고 재귀를 돌리고 있다. 
            
            allPossibleFBT(leftCount)
            allPossibleFBT(rightCount) 
            
           	왼쪽 트리노드와 오른쪽 트리노드를 결합한다. 
            TreeNode root = new TreeNode(0); 
            root.left = left; 
            root.right = right; 
            result.add(root); 
        }
        memo.put(n , result);
        return result ;
    }
}