뒤죽박죽 코딩 이야기

2022년 09월 29일 목요일 - 어제 다비치 영접함!!

오늘 올려볼 문제는 658번 Find K Closest Elements 이라는 문제이다.

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

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

오랜만에 올리는 미디엄 문제같네...

입력

사진에서도 볼 수 있듯이 정렬된 int 배열 1개와 int 값 2개가 입력으로 들어온다.

풀이 및 코드

x와 가장 가까운 원소들로만 이루어진 길이가 k인 subarray를 찾는 문제이다.

이 때 차이는 절대값으로 판별하고 절대값이 작을 때는 원소가 더 작은쪽을 택한다.

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

Queue에 원소들을 넣어두고 넣은 값들과 x 차이의 합을 구한다.

이후 window slide를 사용하여 합이 커지는 순간 직전까지 찾고 리턴하는 방식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        Queue<Integer> q = new LinkedList<>();
        int sum = 0;
        for(int i = 0; i < k; i++) {
            q.add(arr[i]);
            sum += Math.abs(arr[i] - x);
        }
        
        for(int i = k; i < arr.length; i++) {
            int num = Math.abs(arr[i] - x) - Math.abs(q.peek() - x);

            if(0 <= num && q.peek() < arr[i]) break;
            
            q.poll();
            q.add(arr[i]);
            sum += num;
            continue;
        }
        
        return (List)q;
    }
}

제출 화면

오늘 자바 서버가 별로 안좋은지 속도가 생각보다 안나온다.

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

2022년 09월 22일 목요일 - 와 너무 오랜만!

오늘 올려볼 문제는 557번 Reverse Words in a String III 이라는 문제이다.

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

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

아니 요즘 바빠서 회사에서 문제 풀 수가 없어...

입력

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

풀이 및 코드

공백을 기준으로 단어들을 나누고 단어의 순서는 유지하되 단어는 뒤집은 String을 리턴하는 문제다.

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

공백기준으로 String을 나누고 각자 reverse를 해줘야 하는데 String 메소드에는 없어서 sb로 감싸는 함수를 만들어서 처리했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        for(String str : s.split(" ")) sb.append(reverse(str) + " ");
        return sb.toString().trim();
    }
    
    public String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}

제출 화면

아니 어떻게 String 메소드에 reverse가 없는지 도저히 이해를 할 수가 없다.

코틀린이 너무 편해~~

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

2022년 09월 08일 목요일 - 으아아아아아 이제 4일동안 쉰다!!!!!

오늘 올려볼 문제는 94번 Binary Tree Inorder Traversal 이라는 문제이다.

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

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

너무 쉽자너

입력

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

풀이 및 코드

해당 트리를 inorder traversal 한 결과를 리턴하는 문제다.

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

뭐 이정도는 기본이니 설명은 생략하겠다.

이제 코드를 봐보자!

풀이코드

class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        inOrder(root);
        return result;
    }
    
    public void inOrder(TreeNode root) {
        if(root == null) return;
        
        inOrder(root.left);
        
        result.add(root.val);
        
        inOrder(root.right);
    }
}

제출 화면

이제 트리 좀 그만....

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

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

제출 화면

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

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

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

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