뒤죽박죽 코딩 이야기

2023년 03월 19일 일요일 - T1 가보자고!!

오늘 올려볼 문제는 211번 Design Add and Search Words Data Structure 이라는 문제이다.

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

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

요즘 구현문제가 많네?

입력

이 문제는 입력을 설명하기 힘들다 문제를 참고해주길 바란다.

풀이 및 코드

WordDictionary라는 자료구조를 디자인하고 구현하는 문제이다.

addWord 메소드를 통해서 단어 저장이 가능하고 search 메소드를 통해서 단어 저장 여부를 알 수 있다.

이 때 search로 들어오는 단어는 '.'을 포함하고 있을 수 있고 이 '.'은 모든 문자로 대체 가능하다.

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

이전에 구현했었던 Trie를 사용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class WordDictionary {
    Trie trie = new Trie();
    
    public void addWord(String word) {
        trie.insert(word);
    }
    
    public boolean search(String word) {
        return trie.find(word);
    }
}

class Trie {
    Trie[] tries = new Trie[26];
    boolean isEnd = false;
    
    public void insert(String word) {
        var trie = this;
        for(var c : word.toCharArray()) {
            int index = c - 'a';
            if(trie.tries[index] == null) trie.tries[index] = new Trie();
            trie = trie.tries[index];
        }
        trie.isEnd = true;
    }
    
    public boolean find(String word) {
        if(word.isEmpty()) return isEnd;
        
        var c = word.charAt(0);
        
        if(c == '.') {
            for(int i = 0; i < tries.length; i++) 
                if(tries[i] != null && tries[i].find(word.substring(1))) return true;
            
            return false;
        } 
        
        return tries[c - 'a'] != null && tries[c - 'a'].find(word.substring(1));
    }
}

제출 화면

요즘 구현문제가 많아서 클린 코드를 연습하기 좋은 것 같다.

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

2023년 03월 18일 토요일 - 힘드러잉

오늘 올려볼 문제는 1472번 Design Browser History 이라는 문제이다.

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

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

어제 취해서 올리는걸 까먹음..

입력

이 문제는 입력을 설명하기가 복잡하다 문제를 참고해주길 바란다.

풀이 및 코드

문제 제목에서도 볼 수 있듯이 Browser History를 구현하는 문제이다.

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

Stack 2개 사용하는 식으로 문제를 풀면된다!

이제 코드를 봐보자!

풀이코드

class BrowserHistory {
    Stack<String> backUrls = new Stack<>();
    Stack<String> forwardUrls = new Stack<>();
    String currentUrl;

    public BrowserHistory(String homepage) {
        currentUrl = homepage;
    }
    
    public void visit(String url) {
        forwardUrls.clear();
        backUrls.push(currentUrl);
        currentUrl = url;
    }
    
    public String back(int steps) {
        int size = Math.min(backUrls.size(), steps);
        
        for(int i = 0; i < size; i++) {
            forwardUrls.push(currentUrl);
            currentUrl = backUrls.pop();
        }
        
        return currentUrl;
    }
    
    public String forward(int steps) {
        int size = Math.min(forwardUrls.size(), steps);
        
        for(int i = 0; i < size; i++) {
            backUrls.push(currentUrl);
            currentUrl = forwardUrls.pop();
        }
        
        return currentUrl;
    }
}

제출 화면

알고리즘 공유회가 스터디가 되어가는게 눈에 보이기 시작한다.

열심히 진행해서 모두에게 도움되는 스터디로 만들어봐야지!!

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

2023년 03월 15일 수요일 - 본격적으로 알고리즘 스터디를 해봅시다

오늘 올려볼 문제는 958번 Check Completeness of a Binary Tree 이라는 문제이다.

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

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

생각보다는 오래걸림...

입력

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

풀이 및 코드

Binary Tree가 complete한지 판단하는 문제이다.

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

그냥 전형적인 bfs 문제

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        var q = new LinkedList<TreeNode>();
        q.add(root);
        var emptyOccurred = false;
        
        while(!q.isEmpty()) {
            int size = q.size();
            for(int i = 0; i < size; i++) {
                var now = q.poll();
                
                if(now == null) {
                    emptyOccurred = true;
                    continue;
                } 
                
                if(emptyOccurred) return false;
                
                q.add(now.left);
                q.add(now.right);
            }
        }
        
        return true;
    }
}

제출 화면

이제 알고리즘 사람들이 많아지면서 문서화도 하고 자동화도 붙이고 깃헙도 쓰고 하는 본격적인 스터디로 만들어나갈 예정이다.

화이팅!!!

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

2023년 03월 14일 화요일 - 오랜만이구만

오늘 올려볼 문제는 129번 Sum Root to Leaf Numbers 이라는 문제이다.

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

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

왜 요즘 문제가 잘 안풀리지..

입력

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

풀이 및 코드

root 노드부터 leaf 노드까지의 길을 한 숫자라고 봤을 때 해당 바이너리 트리에서 나오는 모든 숫자의 합을 구하는 문제이다.

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

dfs 사용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    int result = 0;
    
    public int sumNumbers(TreeNode root) {
        if(root != null) solve(root, 0);

        return result;
    }
    
    private void solve(TreeNode root, int num) {
        if(root.left == null && root.right == null) {
            result += num * 10 + root.val;
            return;
        }
        
        if(root.left != null) solve(root.left, num * 10 + root.val);
        if(root.right != null) solve(root.right, num * 10 + root.val);
    }
}

제출 화면

요즘따라 쉬운문제도 잘 못 풀고 그런다...

더 분발해야지...

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

2023년 03월 08일 수요일 - 개강 파티!

오늘 올려볼 문제는 875번 Koko Eating Bananas 이라는 문제이다.

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

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

아니 왜 이렇게 약속이 많이 잡히지...?

입력

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

풀이 및 코드

koko가 한 시간에 k개의 바나나만 먹을 수 있다.

바나나 뭉치들이 있을 때 주어진 h 시간내로 먹을 수 있으면서 최소인 k값을 구하는 문제이다.

한 번에 한 뭉치만 먹어야하고 해당 뭉치에 k개 이하의 바나나가 남았다면 모두 먹는다.

다른 뭉치와 같이 먹는 것은 불가능하다.

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

어제 문제와 비슷하게 바이너리 서치로 푸는 문제이다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1, right = 0;
        for(var p : piles) right = Math.max(right, p);
        
        while(left < right) {
            int mid = left + (right - left) / 2, hour = 0;
            
            for(var p : piles) hour += p / mid + (p % mid == 0 ? 0 : 1);
            
            if(hour > h) left = mid + 1;
            else right = mid;
        }
        
        return left;
    }
}

제출 화면

이거 옛날에 못 풀고 바이너리 서치로 풀면 된다는 것에 큰 충격을 받았던 문제이다.

그래서 그런지 머리에 각인되어 있어서 쉽게 풀 수 있었던 것 같다.

그리고 나 요즘 왤케 약속 많지?

뭐 근데 이 때 아니면 언제 놀아~~

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

2023년 03월 07일 화요일 - 왜 아직 화욜?

오늘 올려볼 문제는 2187번 Minimum Time to Complete Trips 이라는 문제이다.

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

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

생각보다는 어려운 문제

입력

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

풀이 및 코드

모든 버스가 독립적으로 운행되고 한 번 운행될 때 소요되는 시간들이 주어진다.

버스가 한 번 운행될 때 여행을 한 번 했다고 했을 때 totalTrips만큼 여행하는데 필요한 최소한의 시간이 얼마인지 구하는 문제이다.

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

이진 탐색으로 문제를 풀었다.

시간을 left, right로 두고 mid를 가지고 배열을 순회하면서 비교하는 식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long left = 0, right = 100000000000000l;
        
        while(left < right) {
            long mid = left + (right - left) / 2;
            long midResult = 0;
            
            for(var t : time) midResult += mid / t;
            
            if(midResult < totalTrips) left = mid + 1;
            else right = mid;
        }
        
        return left;
    }
}

제출 화면

나는 휴학생인데 동기들이 개강하면서 나도 바빠졌다...

이게 맞나..?

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

2023년 03월 05일 일요일 - 오랜만이구만

오늘 올려볼 문제는 1345번 Jump Game IV 이라는 문제이다.

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

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

하드치고는 쉬웠다!

입력

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

풀이 및 코드

0번째 index에서 마지막 index로 가는 가장 짧은 점프 횟수를 구하는 문제이다.

아래 3가지 방법으로 점프가 가능하다.

1. 0보다 크거나 같은 index - 1
2. 배열의 크기보다 작은 index + 1
3. arr[i] == arr[j] 인 j

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

bfs를 하는데 이미 방문했던 곳은 다시 갈 필요가 없으므로 visit 배열도 만들어서 활용했다.

또한 이미 방문한 곳에 원소값에 해당하는 index들은 이미 queue에 들어갔거나 들어있으므로 다시 넣는 과정을 거치지 않는다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minJumps(int[] arr) {
        var visit = new boolean[arr.length];
        var map = new HashMap<Integer, ArrayList<Integer>>();
        
        for(int i = 0; i < arr.length; i++) {
            var num = arr[i];
            if(!map.containsKey(num)) map.put(num, new ArrayList<>());
            map.get(num).add(i);
        }
        
        var q = new LinkedList<Integer>();
        q.add(0);
        
        for(int jump = 0; jump < arr.length; jump++) {
            int size = q.size();
            for(int i = 0; i < size; i++) {
                var now = q.poll();
                
                if(now == arr.length - 1) return jump;
                
                if(now - 1 > 0 && !visit[now - 1]) q.add(now - 1);
                if(!visit[now + 1]) q.add(now + 1);
                
                if(visit[now]) continue;
                
                visit[now] = true;
                
                for(var index: map.get(arr[now])) {
                    if(visit[index]) continue;
                    visit[index] = true;
                    q.add(index);
                }
            }
        }
        
        return arr.length - 1;
    }
}

제출 화면

생각보다는 오래걸렸는데 조금 처리를 잘못해서 오래걸린 것이라서 실수를 조금 덜하도록 노력해야 할 것 같다.

그래도 하드 문제인 것 치고는 잘 풀어서 맘에 든다.

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

2023년 03월 01일 수요일 - 대황T1!

오늘 올려볼 문제는 912번 Sort an Array 이라는 문제이다.

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

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

오랜만에 sort 구현해봤네 ㅎㅎ

입력

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

풀이 및 코드

시간 복잡도 nlogn 인 정렬을 직접 구현하는 문제이다.

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

머지소트로 진행했다~

이제 코드를 봐보자!

풀이코드

class Solution {
    int[] arr;
    public int[] sortArray(int[] nums) {
        arr = nums;
        sort(0, nums.length - 1);
        return arr;
    }
    
    public void sort(int left, int right) {
        int mid = left + (right - left) / 2;
        if(right - left > 1) {
            sort(left, mid);
            sort(mid + 1, right);
            merge(left, mid, mid + 1, right);
        } else {
            if(arr[left] > arr[right]) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
    }
    
    public void merge(int ls, int le, int rs, int re) {
        var tArr = new int[re - ls + 1];
        int li = ls, ri = rs;
        
        for(int i = 0; i < tArr.length; i++) {
            if(li <= le && ri <= re) 
                tArr[i] = arr[arr[li] < arr[ri] ? li++ : ri++];
            else if(li > ls && ri <= re) 
                tArr[i] = arr[ri++];
            else 
                tArr[i] = arr[li++];
        }
        
        for(int i = 0; i < tArr.length; i++) arr[ls + i] = tArr[i];
    }
}

제출 화면

뭔가 오랜만에 이런 구현을 직접해서 그런지 예쁘게 구현하지는 못한것 같다.

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