뒤죽박죽 코딩 이야기

2023년 03월 22일 수요일 - PO 꿀잼

오늘 올려볼 문제는 2492번 Minimum Score of a Path Between Two Cities 이라는 문제이다.

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

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

왜 아직도 수욜이니

입력

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

풀이 및 코드

1번 노드부터 n번 노드까지 있는 그래프가 있다.

roads를 통해서 이어져있는 길과 길의 길이를 입력으로 준다.

이 때 1번 노드부터 n번 노드로 가는 길 중에 가장 짧은 노드 사이의 거리의 길이를 구하는 문제이다. (설명하기가 힘들다..)

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

Union Find로 1번 노드와 연결된 노드들을 구하고 최소값을 구했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minScore(int n, int[][] roads) {
        int[] arr = new int[n + 1];
        
        for(int i = 0; i < n + 1; i++) arr[i] = i;
        
        for(var road : roads) {
            int a = findUnion(arr, road[0]);
            int b = findUnion(arr, road[1]);
            
            if(a < b) arr[b] = a;
            else arr[a] = b;
        }
        
        int result = Integer.MAX_VALUE;
        
        for(var road : roads) {
            if(findUnion(arr, road[0]) == 1) result = Math.min(result, road[2]);
        }
        
        return result;
    }
    
    private int findUnion(int[] arr, int n) {
        if(arr[n] == n) return n;
        
        return findUnion(arr, arr[n]);
    }
}

제출 화면

어후 요즘 너무 졸려

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

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

오늘 올려볼 문제는 2348번 Number of Zero-Filled Subarrays 이라는 문제이다.

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

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

이게 왜 이지가 아님?

입력

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

풀이 및 코드

0으로만 이루어진 subarray의 총 개수를 구하는 문제이다.

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

0으로만 이루어진 subarray의 길이를 구하는 과정에서 모든 길이를 더해주면 답이 나온다. (0으로만 이루어진 배열에서 만들 수 있는 subarray의 개수가 1부터 n까지의 합과 같기 때문)

이제 코드를 봐보자!

풀이코드

class Solution {
    public long zeroFilledSubarray(int[] nums) {
        int length = 1;
        long result = 0;
        
        for(var num: nums) {
            if(num == 0) result += length++;
            else length = 1;
        }
        
        return result;
    }
}

제출 화면

알고리즘 스터디를 진행했더니 블로그 쓰는걸 까먹을 뻔 했다 ㅎㅎ

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

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

제출 화면

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

이게 맞나..?

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