뒤죽박죽 코딩 이야기

2022년 09월 07일 수요일 - 내일만... 버티면... 쉰다...!

오늘 올려볼 문제는 606번 Construct String from Binary Tree 이라는 문제이다.

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

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

근데 오늘 왜 easy문제인지 잘 모르겠음;;

입력

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

풀이 및 코드

Binaray Tree를 괄호를 사용한 방식의 Stringd으로 바꾸라는 문제인데.. 제대로 설명하기 힘드니 문제를 참고하길..

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

dfs를 돌면서 String Builder에 괄호와 value를 넣는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    StringBuilder sb = new StringBuilder();
    public String tree2str(TreeNode root) {
        solve(root);
        return sb.toString();
    }
    
    public void solve(TreeNode root) {
        if(root.left == null && root.right == null) {
            sb.append(root.val);
            return;
        }
        sb.append(root.val + "(");
        if(root.left != null) solve(root.left);
        sb.append(")");
        if(root.right != null) {
            sb.append("(");
            solve(root.right);
            sb.append(")");
        }
    }
}

제출 화면

왼쪽 노드는 비어있어도 빈괄호를 넣어주고 오른쪽 노드는 비어있으면 생략하는 것 때문에 조금 해맸다.

이제 트리문제 말고 다른 문제 나왔으면..

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

2022년 09월 06일 화요일 - 왜 아직 화요일?

오늘 올려볼 문제는 814번 Binary Tree Pruning 이라는 문제이다.

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

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

이제는 이런 문제 많이 봐서 그런지 잘 풀린다!

입력

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

풀이 및 코드

모든 SubTree의 값이 전부 0인 SubTree들을 제거한 후에 리턴하는 문제이다.

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

왼쪽, 오른쪽 노드가 각각 null이면 true, value가 0이면 true 이렇게 해서 dfs를 돌렸다.

또한 저 값들을 기준으로 노드를 제거해나가는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if(solve(root)) root = null;
        return root;
    }
    
    public boolean solve(TreeNode root) {
        boolean left = false, right = false, value = root.val == 0;
        
        if(root.left == null || root.left != null && solve(root.left)) {
            root.left = null;
            left = true;
        }
        
        if(root.right == null || root.right != null && solve(root.right)) {
            root.right = null;
            right = true;
        }
        
        return left && right && value;
    }
}

제출 화면

원래 이런 문제 풀 때 정말 더럽게 풀었었는데 이제 경험이 좀 쌓였는지 잘 풀리는 것 같다.

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

2022년 09월 05일 월요일 - 비야 그만와라...

오늘 올려볼 문제는 429번 N-ary Tree Level Order Traversal 이라는 문제이다.

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

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

태풍이 오는데 재택 근무 안해??

입력

사진에서도 볼 수 있듯이 Tree의 루트 노드가 입력으로 들어온다.

풀이 및 코드

각 레벨에 맞게끔 분류해서 리턴하는 문제다.

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

그냥 bfs 썼다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        if(root == null) return new ArrayList<>();
        
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        
        List<List<Integer>> result = new ArrayList<>();
        
        while(!q.isEmpty()) {
            int size = q.size();
            
            List<Integer> temp = new ArrayList<>();
            
            for(int i = 0; i < size; i++) {
                Node now = q.poll();
                
                temp.add(now.val);
                
                List<Node> list = now.children;
                
                for(int j = 0; j < list.size(); j++) {
                    q.add(list.get(j));
                }
            }
            
            result.add(temp);
        }
        
        return result;
    }
}

제출 화면

비가 이렇게 많이 오는데 회사를 가야한다니... 두렵다....

사실 두렵지는 않고 너무 귀찮다....

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

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();
    }
}

제출 화면

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

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

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

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

2022년 08월 17일 수요일 - 요즘 쉬운 문제밖에 못푸는 거 같어..

오늘 올려볼 문제는 804번 Unique Morse Code Words 이라는 문제이다.

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

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

문제 대충보고 이게 왜 easy야 라고 생각했었다 ㅋㅋㅋㅋ

입력

사진에서도 볼 수 있듯이 String 배열 1개가 입력으로 들어온다.

풀이 및 코드

String 배열에 들어있는 String 원소를 주어진 모스 부호로 치환했을 때 나오는 형식이 몇개 있는지 구하여 리턴하는 문제다.

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

모스 부호는 상수 배열로 선언해두고 만들어진 모스부호는 HashSet에 넣어두어서 중복을 처리하는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] arr = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        
        HashSet<String> set = new HashSet<>();
        int result = 0;
        
        for(String word : words) {
            StringBuilder sb = new StringBuilder();
            
            for(char c : word.toCharArray()) sb.append(arr[c - 'a']);
            
            if(!set.contains(sb.toString())) {
                set.add(sb.toString());
                result++;
            }
        }
        
        return result;
    }
}

제출 화면

요즘 회사에서 캡처하는게 편하다보니 회사에 있을 때 문제를 못 풀면 블로그를 올리기 힘들어지는 것 같다.

즉... 블로그에 점점 쉬운 문제만 올라가는 안좋은 현상이 일어나는듯....

앞으로는 머리가 휙휙 돌아가서 어려운 문제도 똭 풀어서 블로그에 올렸으면 좋겠다.

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

2022년 08월 16일 화요일 - 화요일인데... 월요일같아....

오늘 올려볼 문제는 387번 First Unique Character in a String 이라는 문제이다.

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

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

아오 집에서 문제 풀 때는 블로그 올리기 힘들어서 회사에서 푼 문제만 올리게 되겠네

입력

사진에서도 볼 수 있듯이 String 1개가 입력으로 들어온다.

풀이 및 코드

주어진 String의 원소중 unique 한 원소들 중 가장 앞에 있는 index를 찾아 리턴하는 문제다.

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

queue에 index를 넣으면서 원소의 unique여부를 찾는다.

이후 queue에서 index를 빼면서 unique 한지 한 번더 판단하고 리턴하는 식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int firstUniqChar(String s) {
        int[] arr = new int[26];
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < s.length(); i++) {
            if(arr[s.charAt(i) - 'a']++ == 0) {
                q.add(i);
            }
        }
        
        while(!q.isEmpty()) {
            if(arr[s.charAt(q.peek()) - 'a'] == 1) return q.poll();
            q.poll();
        }
        
        return -1;
    }
}

제출 화면

오늘은 문제가 쉬웠는데 이거보다 더 좋은 방법이 있나 찾아봤었다.

하지만 내가 맘에 드는 답을 찾을 수 없었으니 내가 제일 잘 풀었다고 생각해야겠다 ㅋㅋㅋㅋ

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

2022년 08월 11일 목요일 - 아유 요즘 문제가 안풀려 머리가 그냥 굳었어

오늘 올려볼 문제는 98번 Validate Binary Search Tree 이라는 문제이다.

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

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

요즘따라 문제 접근 방식에 대한 실력이 많이 줄은 것 같다...

입력

사진에서도 볼 수 있듯이 Binary Search Tree의 루트 노드가 입력으로 들어온다.

풀이 및 코드

주어진 Binary Search Tree가 Valid한지 판단하여 리턴하는 문제다.

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

Inorder로 트리를 순회하면서 이전 노드의 값을 기억한다.

만약 이전 노드보다 작은 값을 가진 노드가 나오면 false를 리턴하는 식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    int pre = -1;
    boolean hasPre = false;
    boolean result = true;
    public boolean isValidBST(TreeNode root) {
        solve(root);
        return result;
    }
    
    public void solve(TreeNode root) {
        if(root == null) return;
        
        solve(root.left);
        if(hasPre && pre >= root.val) result = false;
        hasPre = true;
        pre = root.val;
        solve(root.right);
    }
}

제출 화면

오늘 문제도 맨처음 봤을 때는 루트 노드부터 시작해서 어디까지 저장해야하나라는 생각으로 쉬운 방법을 생각하지 못 할 뻔했다.

다행히 Inorder를 생각해내서 문제를 쉽게 풀 수 있었던 것 같다.

요즘 들어서 일이 힘들기도하고 문제를 푸는데 시간을 별로 안들이려고 해서 답을 일찍 보기도 해서 그런지 몰라도 머리가 많이 굳은 것 같다.

내가 못풀고 스터디원들이 푸는 경우도 많아졌다. (물론 바라던 바였지만 내가 실력이 떨어져서 생긴 느낌이 더 강하다.)

다실 실력을 되찾고 싶은 생각이 들지만 그렇다고 시간을 들이기는 또 귀찮으니 굉장히 이기적인 상태에 있는 느낌이다.

하지만 그래도 꾸준히하고는 있으니 나중에 알고리즘 각잡고 할 때는 도움이 되지 않을까 생각하고 있긴하다.

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

2022년 08월 03일 수요일 - 그냥 스크린샷은 윈도우에서 찍자...

오늘 올려볼 문제는 729번 My Calendar I 이라는 문제이다.

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

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

아우 그냥 회사에서 스샷만 찍고 올려야겠어... 맥 스크린샷 너무 불편해...

입력

사진에서도 볼 수 있듯이 메소드에 대한 파라매터로 int값 2개씩 입력으로 들어온다.

풀이 및 코드

이중 예약이 되지 않게끔 캘린더 클래스를 구현하는 문제다.

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

TreeMap을 사용해서 근사값을 구하고 이를 통해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class MyCalendar {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    
    public MyCalendar() {
        
    }
    
    public boolean book(int start, int end) {
        int s = -1, e = -1;
        if(map.floorKey(start) != null) {
            s = map.floorKey(start);
        }
        
        if(map.floorKey(--end) != null) {
            e = map.floorKey(end);
        }
        
        // start와 end의 floorKey값이 다르면 무조건 다른 일정과 겹쳐있다는 뜻이라서 이 구문 넣어줌
        if(s - e != 0) return false;
        
        if(s != -1 && start <= map.get(s)) return false;
        
        if(e != -1 && end <= map.get(e)) return false;
        
        map.put(start, end);
        
        return true;
    }
}

제출 화면

오늘 문제는 주석 처리한 부분을 생각하지 못해서 생각보다 많이 틀렸다.

그리고 아오 맥은 스크린샷 매번 위치 지정해주는게 힘들어서 그냥 회사 윈도우에서 스크린샷만 찍어서 올려야겠다.

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