뒤죽박죽 코딩 이야기

2022년 09월 01일 목요일 - 감바스 꿀맛 노래방 꿀잼

오늘 올려볼 문제는 1448번 Count Good Nodes in Binary Tree 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

요즘 회사에서는 문제 못풀겠어.. 바뻐..

입력

사진에서도 볼 수 있듯이 Binary Tree root node가 입력으로 들어온다.

풀이 및 코드

탐색을 하면서 해당 노드가 루트 노드로 부터 오는 길에 해당 노드보다 큰 값이 없었다면 good 노드라고 한다.

이 때 주어진 트리에 good 노드가 몇개인지 구하여 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈다.

dfs를 하면서 Stack에 여태까지 탐색한 노드의 값을 넣는데 최대값들만 넣는다.

그렇게 Stack 맨 마지막 값과 현재 노드 값을 비교해서 good 노드를 찾는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    Stack<Integer> s = new Stack<>();
    int result = 0;
    public int goodNodes(TreeNode root) {
        s.push(-10005);
        dfs(root);
        return result;
    }
    
    public void dfs(TreeNode root) {
        if(root == null) return;
        
        if(s.peek() <= root.val) result++;
        
        s.push(Math.max(s.peek(), root.val));
        
        dfs(root.left);
        
        dfs(root.right);
        
        s.pop();
    }
}

제출 화면

요즘 문제를 풀어도 집에서 많이 풀다보니깐 블로그에는 글을 뜸하게 쓰게 되는거 같다...

맥은 개발할 때 편하지만... 이런 부분에서는 불편하니... 뭔가 맘에 안든다...

내일도 회사에서 잘 풀 수 있었으면 좋겠다!!

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.