[99클럽 코테 스터디] 33일차 TIL - Number of Good Leaf Nodes Pairs

오늘의 학습 키워드

</> 깊이/너비 우선 탐색(DFS/BFS)

공부한 내용 본인의 언어로 정리하기

class Solution {
    int count = 0; // 좋은 쌍의 개수를 저장할 변수

    public int countPairs(TreeNode root, int distance) {
        if (root == null) {
            return 0; // 트리가 비어있으면 0 반환
        }
        dfs(root, distance); // DFS 탐색 시작
        return count; // 최종적으로 계산된 좋은 쌍의 개수를 반환
    }

    private int[] dfs(TreeNode node, int distance) {
        int[] dist = new int[distance + 1]; // 현재 노드에서 리프 노드까지의 거리를 저장하는 배열
        
        if (node == null) {
            return dist; // 노드가 null이면 거리 배열을 그대로 반환
        }

        // 리프 노드인 경우 (자식 노드가 없는 경우)
        if (node.left == null && node.right == null) {
            dist[1] = 1; // 리프 노드까지의 거리가 1이므로 배열의 1번째 위치에 1 저장
            return dist; // 리프 노드의 거리 배열 반환
        }

        // 왼쪽과 오른쪽 자식 노드로 DFS 탐색을 통해 거리 배열을 받아옴
        int[] leftDist = dfs(node.left, distance);
        int[] rightDist = dfs(node.right, distance);

        // 왼쪽과 오른쪽 서브트리의 리프 노드들 간의 거리를 비교하여 좋은 쌍 계산
        for (int i = 1; i <= distance; i++) {
            for (int j = 1; j <= distance; j++) {
                if (i + j <= distance) {
                    count += leftDist[i] * rightDist[j]; 
                    // i 거리와 j 거리의 리프 노드 쌍이 좋은 쌍인지 확인
                }
            }
        }

        // 현재 노드의 거리 정보를 부모 노드로 전달하기 위해 거리를 1씩 증가시킴
        for (int i = 1; i < distance; i++) {
            dist[i + 1] = leftDist[i] + rightDist[i];
        }

        return dist; // 업데이트된 거리 배열을 부모 노드로 반환
    }
}

오늘의 회고

오늘도 여전히 우선탐색 알고리즘 문제가 나왔다. 솔직히 아직 내가 내 능력껏 이해하고 풀이를 하려면 한참 많이 부족한 것 같다. 그래서 오늘도 AI의 힘을 빌려 진행을 했다.
갑자기 풀려고 해도 안풀리고 생각도 안나니까 자괴감오고 의욕이 훅 떨어진다...그래도 어쩔 수 있나..해야지...하나씩 천천히 하다보면 되겠지라는 생각이다. 그래도 한줄 한줄 이해하고 나니 재미가 있긴하다.

오늘도 노드의 거리를 측정하고 그 거리가 distance 이하라면 "좋은 쌍"으로 부르고 "좋은 쌍"의 개수를 새는것이 문제였다.

전과 같이 재귀를 해줄 매서드와 DFS 탐색을 해줄 클래스를 따로 만들어 준다. 오늘은 스택 대신 트리노드가 직접 만들어져 있기 때문에 TreeNode로 진행을 하였다.

DFS로 탐색을 하면서 서브트리의 리프 노드들 간의 거리를 비교해서 좋은 쌍을 계산한다.
두 노드들 간의 거리가 distance보다 작다면 좋은 쌍이므로 갯수를 추가해준다.

그렇게 반환해준 쌍을 최종적으로 출력해주는 문제였다.

AI 코드리뷰

현재 코드의 장점

1. 효율적인 리프 노드 탐색: 코드에서 DFS를 사용하여 트리의 모든 리프 노드를 효율적으로 탐색하고, 각 리프 노드 간의 거리를 계산하고 있습니다.
2. 간결한 논리: 주어진 문제를 해결하기 위해 명확하고 간결한 논리를 따르고 있습니다. DFS를 사용하여 서브트리 내 리프 노드 간의 거리를 계산하고, 조건에 맞는 "좋은 쌍"을 효과적으로 카운트합니다.
3. 재귀 구조의 활용: 재귀를 통해 DFS를 구현함으로써 코드의 가독성과 간결성을 높였습니다. 재귀 호출을 통해 스택을 사용하지 않고도 DFS를 구현했습니다.

현재 코드의 단점

1. 메모리 사용: 각 노드에서 distance + 1 크기의 배열을 생성하므로, 깊은 트리일수록 메모리 사용량이 증가할 수 있습니다. 특히, 모든 노드에 대해 이러한 배열을 생성하기 때문에 트리의 깊이가 깊을수록 메모리 사용이 늘어납니다.
2. 중복 계산: 코드가 각 노드마다 왼쪽과 오른쪽 서브트리의 거리 배열을 생성하여 리프 노드 간의 거리를 계산하는데, 이 과정에서 동일한 계산이 반복될 가능성이 있습니다.
3. 복잡한 거리 계산: 이중 반복문을 통해 왼쪽과 오른쪽 서브트리의 거리 배열을 비교하는 과정에서, 최악의 경우 O(distance^2)의 복잡도가 추가로 발생할 수 있습니다.

시간 복잡도

• 탐색 시간: 트리의 각 노드를 한 번씩 방문하므로, 기본적인 DFS 탐색의 시간 복잡도는 O(N)입니다.
• 거리 계산 시간: 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리 간의 거리 비교를 수행하는데, 이중 반복문을 사용하여 최대 O(distance^2)의 시간 복잡도를 추가로 필요로 합니다.
• 최종 시간 복잡도: O(N * distance^2)입니다.

개선된 코드 리뷰

class Solution {
    int count = 0;

    public int countPairs(TreeNode root, int distance) {
        if (root == null) {
            return 0;
        }
        dfs(root, distance);
        return count;
    }

    private List<Integer> dfs(TreeNode node, int distance) {
        List<Integer> distList = new ArrayList<>();

        if (node == null) {
            return distList;
        }

        if (node.left == null && node.right == null) {
            distList.add(1); // 리프 노드까지의 거리 1 추가
            return distList;
        }

        List<Integer> leftDist = dfs(node.left, distance);
        List<Integer> rightDist = dfs(node.right, distance);

        // 왼쪽과 오른쪽 서브트리의 리프 노드들 간의 거리 계산
        for (int l : leftDist) {
            for (int r : rightDist) {
                if (l + r <= distance) {
                    count++;
                }
            }
        }

        // 현재 노드의 거리 정보 업데이트
        for (int l : leftDist) {
            if (l + 1 <= distance) distList.add(l + 1);
        }
        for (int r : rightDist) {
            if (r + 1 <= distance) distList.add(r + 1);
        }

        return distList;
    }
}

개선된 버전의 장점

1. 메모리 사용 최적화: 배열 대신 리스트를 사용하여 불필요한 공간 할당을 줄였습니다. 리스트를 사용함으로써 필요한 거리 정보만을 저장하게 됩니다.
2. 유연한 거리 처리: 리스트를 사용해 각 노드에서 리프 노드까지의 거리를 유연하게 처리할 수 있습니다.

개선된 버전의 단점

1. 시간 복잡도: 시간 복잡도 자체는 크게 변화하지 않으며, 여전히 O(N * distance^2)입니다.
2. 추가적인 연산 비용: 배열을 사용할 때보다 리스트의 추가와 비교 연산이 약간 더 느릴 수 있습니다.

시간 복잡도

• 시간 복잡도는 본래 코드와 동일한 O(N * distance^2) 이지만, 메모리 사용이 최적화되었습니다. 따라서 매우 큰 트리에 대해서는 메모리 사용 측면에서 이점이 있을 수 있습니다.

---

내일 공부할 것 :

알고리즘과 문제가 길어지거나 영어로 된 문제가 되면 문제 이해도가 매우 약하다. 다른 문제를 더 찾아봐야겠다. LEETCODE 출제된 문제 밑에 보면 연관 알고리즘과 문제들이 나온다.

문제

https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/?envType=daily-question&envId=2024-07-18