99클럽 코테 스터디 13일차 TIL + [LeetCode] 1302. Deepest Leaves Sum JAVA풀이/DFS/멀티해시맵

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

DFS

멀티해시맵

 

 

 

2. 오늘의 학습 문제 

---

문제

---

 

https://leetcode.com/problems/deepest-leaves-sum/description/

 

 

 

코드

---

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 
/*
1. 멀티해시맵에 키:밸류=depth:노드값 리스트 를 선언한다.
2. 노드를 DFS순회하여 최하단 노드일시 멀티해시맵에 값을 저장한다.
3. 멀티해시맵에서 가장 큰 키의 값들을 더해 반환한다. 
 
*/
import java.util.*;
 
class Solution {
 
    static Map<String, List<Integer>> multiMap; 
 
    public int deepestLeavesSum(TreeNode root) {
        multiMap= new HashMap<String, List<Integer>>() ; //멀티해시맵 선언, 키:밸류= dpeth:노드값리스트
        DFS(root, 0); 
         Set<String> keys = multiMap.keySet();
 
        String maxKey = Collections.max(keys, Comparator.comparingInt(Integer::parseInt)); //가장 큰 수의 키 찾기. 
 
        return getSumOfValues(multiMap, maxKey); //가장 큰 키에 대한 밸류값합 반환
    }
 
    public void DFS(TreeNode node, int depth){
 
        if(node.left!=null){ //왼쪽 자식 있을 때
            DFS(node.left, depth+1);
        }
        if(node.right!=null){ //오른쪽 자식 있을 때
            DFS(node.right, depth+1);
        }
        if(node.left== null && node.right==null){ //최하단 노드면
            String key=String.valueOf(depth);
            if(!multiMap.containsKey(key)){ //멀티맵에 depth키가 업으면 추가
                multiMap.put(key, new ArrayList<Integer>());
            }
            multiMap.get(key).add(node.val); //노드의 밸류 추가
        }
            
    }
 
    public static int getSumOfValues(Map<String, List<Integer>> mMap, String maxKey){
 
        List<Integer> values= mMap.get(maxKey) ; //키에 대한 값들을 리스트에 저장
        int sum=0;
        for(int value :values){ //키에 대한 값들을 더함
            sum+=value;
        }
        return sum;
    }
 
}

 

1. 멀티해시맵에 키:밸류=depth:노드값 리스트 를 선언한다.

2. 노드를 DFS순회하여 최하단 노드일시 멀티해시맵에 값을 저장한다.

3. 멀티해시맵에서 가장 큰 키의 값들을 더해 반환한다.

 

 

 

 런타임이 9ms로 길게 나왔는데, 해시맵에 일일이 저장하지 않고, maxDepth와 sum을 저장하고 최하단노드일때 현재 depth를 비교하고 같으면 sum을 더하고, depth가 maxDepth보다 크면 값을 갱신하는 식으로 설정하면 메모리를 더 적게 쓸 것이다. 

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 
/*
1. 최대깊이 maxDepth와 합계 sum을 전역변수 설정한다.
2. 노드를 DFS순회하여 최하단 노드일시 masDepth와 비교하여 sum을 갱신한다.
3. DFS순회가 완료되면 sum을 반환한다. 
 
*/
import java.util.*;
 
class Solution {
 
    static int maxDepth;
    static int sum;
    public int deepestLeavesSum(TreeNode root) {
        maxDepth=0;
        sum=0;
        DFS(root, 0); 
        
        return sum; //가장 큰 키에 대한 밸류값합 반환
    }
 
    public void DFS(TreeNode node, int depth){
 
        if(node.left!=null){ //왼쪽 자식 있을 때
            DFS(node.left, depth+1);
        }
        if(node.right!=null){ //오른쪽 자식 있을 때
            DFS(node.right, depth+1);
        }
        if(node.left== null && node.right==null){ //최하단 노드면
            if(depth==maxDepth){ //maxDepth와 같다면 sum에 합산
                sum+=node.val;
            }
            else if( depth>maxDepth){ //maxDepth를 갱신하고 sum초기화
                maxDepth=depth;
                sum=node.val;
            }
        }
            
    }
 
 
}

 

그렇게 새로 코드를 작성했는데, 1ms로 시간이 단축되었다.

 

3. 오늘의 회고

---

• 리트코드에는 런타임을 다른 유저와 비교할 수 있어서, 더 효율적으로 코드를 작성하여 메모리를 줄이고 시간을 높이는 방법에 대해 고민할 수 있다. 이번에는 그렇게 하여 시간을 단축시키는 코드를 새로 작성해보았다.
• 어제 TIL작성을 하지 못해서 TIL챌린지가 0일차로 초기화됐다 🥺 6월 한 달간 매일 작성하여 TIL챌린지 28일 작성을 달성해보자.  

99클럽

코딩테스트 준비

개발자 취업

항해99

TIL