뒤죽박죽 코딩 이야기

2023년 02월 01일 수요일 - 아니 아직도 수욜이라고?

오늘 올려볼 문제는 1071번 Greatest Common Divisor of Strings 이라는 문제이다.

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

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

아지지만... 진짜 다른 사람 풀이 개섹시함

입력

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

풀이 및 코드

두 String을 모두 나눌 수 있는 String 중에서 가장 긴 String을 구하는 문제이다.

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

짧은 String을 구해서 substring으로 하나씩 비교했다. (bruteforce)

이제 코드를 봐보자!

풀이코드

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        var str = str1.length() > str2.length() ? str1 : str2;
        
        for(int i = str.length(); i > 0; i--) {
            var div = str.substring(0, i);
            
            if(str1.replace(div, "").length() == 0 && str2.replace(div, "").length() == 0) return div;
        }
        
        return "";
    }
}

제출 화면

오늘 discuss에 올라와있는 개쩌는 답안을 봤는데 너무 섹시했다.

나도 저런걸 혼자 떠올리는 날이 오기를...

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

2023년 01월 30일 월요일 - 아직도 1월이라고?

오늘 올려볼 문제는 1137번 N-th Tribonacci Number 이라는 문제이다.

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

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

너무 쉽다..

입력

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

풀이 및 코드

피보나치와 비슷한 트리보나치 수열을 구하는 문제이다.

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

조금 빠르게 나오게 하기 위해서 static 배열을 사용했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    static int[] arr = new int[38];
    
    public Solution() {
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 1;
    }
    
    public int tribonacci(int n) {
        for(int i = 3; i <= n && arr[n] == 0; i++) arr[i] = arr[i - 3] + arr[i - 2] + arr[i - 1];
        return arr[n];
    }
}

제출 화면

뭐 오늘은 1분 컷...

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

2023년 01월 29일 일요일 - 허허 이렇게 늦은 시간에 글을 쓰다니...

오늘 올려볼 문제는 460번 LFU Cache 이라는 문제이다.

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

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

유지보수 안할거라고 블로그 자동화 대충 만들어놓았던 나를 후회한다....

입력

사진에서도 볼 수 있듯이 다양한 파라매터가 입력으로 들어온다.

풀이 및 코드

LFU Cache를 구현하는 문제이다.

기본적으로 capacity를 받아서 최대로 저장할 수 있는 캐시의 양을 받는다.

이후 put또는 get 메소드를 통해서 cache에 접근하고 값을 추가하는데 아래와 같은 규칙을 따른다.

put을 통해서 캐시에 k-v 형태로 값을 넣는다.

이 때 캐시의 capacity가 넘어가게 되면 cnt(key)값이 가장 작은 값을 지우고 새로운 값을 넣는다.

이 때 cnt(key)의 값이 같은 key들이 여러개 존재한다면 가장 오래전에 쓰인 값을 지운다.

cnt(key)가 올라가는 기준은 get, put 메소드에 불릴 때 마다이다.

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

1. 캐시의 k-v 값을 저장할 hashmap
2. key의 cnt값을 저장할 hashmap
3. cnt값을 key로 두고 해당 cnt를 가지고 있는 키를 순서대로 저장하고 있을 treemap

이 세가지를 사용했다. 자세한 사항은 구현을 보면 알 수 있을 것이다.

이제 코드를 봐보자!

풀이코드

class LFUCache {
    int capacity, minCnt = 0;
    HashMap<Integer, Integer> cnt = new HashMap<>();
    TreeMap<Integer, LinkedHashSet<Integer>> lru = new TreeMap<>();
    HashMap<Integer, Integer> cache = new HashMap<>();
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(!cache.containsKey(key)) return -1;
        
        int prevCnt = cnt.get(key), nowCnt = prevCnt + 1;
        cnt.put(key, nowCnt);
        
        lru.get(prevCnt).remove(key);
        if(lru.get(prevCnt).isEmpty()) lru.remove(prevCnt);
        
        if(!lru.containsKey(nowCnt)) lru.put(nowCnt, new LinkedHashSet<>());
        lru.get(nowCnt).add(key);
        
        return cache.get(key);
    }
    
    public void put(int key, int value) {
        if(capacity == 0) return;
        if(!cache.containsKey(key) && capacity == cache.size()) {
            int minCnt = lru.firstKey(), minKey = -1;
            var itr = lru.get(minCnt).iterator();

            if(itr.hasNext()) minKey = itr.next();
            
            cache.remove(minKey);
            lru.get(minCnt).remove(minKey);
            cnt.remove(minKey);
        }
        
        int prevCnt = cnt.getOrDefault(key, 0), nowCnt = prevCnt + 1;
        cache.put(key, value);
        cnt.put(key, nowCnt);
        
        if(lru.get(prevCnt) != null) {
            lru.get(prevCnt).remove(key);
            if(lru.get(prevCnt).isEmpty()) lru.remove(prevCnt);
        }
        
        if(!lru.containsKey(nowCnt)) lru.put(nowCnt, new LinkedHashSet<>());
        lru.get(nowCnt).add(key);
    }
}

제출 화면

어려워보였지만 풀어서 뿌듯한 마음에 블로그를 올리고 싶었다!!

다만... 내 블로그 자동화는 12시가 넘어가면 작동하지 않기에 이를 수정하려다가... 너무 시간이 오래걸려서 거의 2시가 되었다..

내일은 좀 힘들 것 같다...

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

2023년 01월 27일 금요일 - 아니 왤케 추워...

오늘 올려볼 문제는 472번 Concatenated Words 이라는 문제이다.

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

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

하드치고는 너무 쉽게 풀어버림...

입력

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

풀이 및 코드

주어진 String들을 이어붙였을 때 만들어낼 수 있는 값중 배열에 있는 모든 값들을 찾아서 리턴하는 문제이다.

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

먼저 String의 길이순으로 정렬한다.

이 후 substring으로 잘라가면서 dfs를 하는 식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    HashSet<String> set = new HashSet<>();
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        var result = new ArrayList<String>();
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        
        for(var w : words) {
            for(int i = 1; i < w.length(); i++) {
                if(set.contains(w.substring(0, i)) && solve(i, w)) {
                    result.add(w);
                    break;
                }
            }
            set.add(w);
        }
        
        return result;
    }
    
    public boolean solve(int start, String word) {
        if(start == word.length()) return true;
        
        for(int i = start + 1; i <= word.length(); i++) if(set.contains(word.substring(start, i)) && solve(i, word)) return true;
        
        return false;
    }
}

제출 화면

이게 되나 싶었는데 이게 됐다... ㄷㄷ

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

2023년 01월 26일 목요일 - 눈이 펑펑 와요

오늘 올려볼 문제는 787번 Cheapest Flights Within K Stops 이라는 문제이다.

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

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

오늘 문제 미디엄치고는 어려웠어요...

입력

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

풀이 및 코드

방향 그래프가 주어지고 최대 들를 수 있는 경유지 개수가 주어졌을 때 목적지로 갈 수 있는 방법 중 가장 짧은 길이를 구하는 문제이다.

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

bfs 를 사용하는데 dp를 섞어서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        HashMap<Integer, Integer>[] arr = new HashMap[n];
        var v = new int[n];
        int result = Integer.MAX_VALUE;
        
        Arrays.fill(v, Integer.MAX_VALUE);
        
        for(var f : flights) {
            if(arr[f[0]] == null) arr[f[0]] = new HashMap<>();
            
            arr[f[0]].put(f[1], f[2]);
        }
        
        var q = new LinkedList<int[]>();
        q.add(new int[]{src, 0});
        
        for(int i = 0; i <= k + 1; i++) {
            int size = q.size();
            for(int j = 0; j < size; j++) {
                var now = q.poll();
                
                if(now[1] > result || v[now[0]] < now[1]) continue;
                if(now[0] == dst) {
                    result = Math.min(result, now[1]);
                    continue;
                }
                if(arr[now[0]] == null) continue;
                
                v[now[0]] = now[1];
                
                for(var key: arr[now[0]].keySet()) q.add(new int[] {key, arr[now[0]].get(key) + now[1]});
            }
        }
        
        return result == Integer.MAX_VALUE ? -1 : result;
    }
}

제출 화면

오늘 오랜만에 출근해서 그런지 힘드러따...

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

2023년 01월 24일 화요일 - 날씨 실화냐?

오늘 올려볼 문제는 909번 Snakes and Ladders 이라는 문제이다.

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

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

생각보다 어려웠던 구현문제..

입력

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

풀이 및 코드

1번부터 시작해서 6까지 있는 주사위를 던져서 맨끝까지 가는 게임이라고 한다.

뱀 또는 사다리가 시작하는 칸에 멈추게 되면 바로 이어져있는 곳으로 이동하게된다고 했을 때 끝가지 갈 수 있다면 가장 적은 횟수를, 갈 수 없다면 -1을 리턴하는 문제이다.

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

일단 판이 그지같으니깐 1차원 배열로 펴준다.

이 후 bfs를 사용하여 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length, index = 1;
        var arr = new int[n * n + 1];
        var v = new boolean[n * n + 1];
        var flag = true;
        
        for(int i = n - 1; i >= 0; i--) {
            if(flag) for(int j = 0; j < n; j++) arr[index++] = board[i][j];
            else for(int j = n - 1; j >= 0; j--) arr[index++] =  board[i][j];
            flag = !flag;
        }
        
        int steps = 0;
        var q = new LinkedList<Integer>();
        q.add(arr[1] == -1 ? 1 : arr[1]);
        
        while(!q.isEmpty()) {
            int size = q.size();
            for(int i = 0; i < size; i++) {
                int now = q.poll();
                if(v[now]) continue;
                v[now] = true;
                
                if(now == n * n) return steps;
                
                for(int j = now + 1; j <= Math.min(now + 6, n * n); j++) q.add(arr[j] == -1 ? j : arr[j]);
            }
            steps++;
        }
        
        return -1;
    }
}

제출 화면

오늘은 날씨가 미친것 같다...

설날 아니었다면 내일 아침 9시 뉴스에 나왔을지도...

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

2023년 01월 23일 월요일 - 아직도 쉰다 ㅎㅎ

오늘 올려볼 문제는 997번 Find the Town Judge 이라는 문제이다.

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

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

쉬는날이라서 그런지 자꾸 알고리즘 스터디를 까먹어..

입력

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

풀이 및 코드

아래 조건에 부합하는 사람이 해당 마을의 심판이다.

1. 심판은 누구도 믿지 않는다.
2. 심판을 제외한 모든 마을 주민들은 심판을 믿는다.
3. 1번, 2번 조건을 만족하는 사람은 딱 한명이다.

이 때 심판을 구하는 문제이다.

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

int 배열하나 만들어서 믿음 받는 개수를 구한다.

이 때 믿는 사람은 -1을 넣어서 1번 조건을 만족하게끔 해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findJudge(int n, int[][] trust) {
        var arr = new int[n + 1];
        for(var t : trust) {
            arr[t[0]] = -1;
            arr[t[1]]++;
        }
        
        for(int i = 1; i <= n; i++) if(arr[i] == n - 1) return i;
        
        return -1;
    }
}

제출 화면

저 코드가 오래걸릴거 같지는 않았는데 순회를 2번 해서 그런지는 몰라도 그렇게 빠른 코드가 아니었다..

leetcode 서버 문제인건지는 잘 모르겠지만 뭐... 그렇다!

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

2023년 01월 21일 토요일 - 설날설날 아주 조아 설날

오늘 올려볼 문제는 93번 Restore IP Addresses 이라는 문제이다.

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

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

leetcode extension 다 만들은듯?

입력

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

풀이 및 코드

입력으로 주어진 String으로 만들 수 있는 valid한 ip주소를 전부 찾아서 리턴하는 문제다.

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

백트래킹 사용하는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    String input;
    ArrayList<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        input = s;
        if(s.length() > 12 || s.length() < 4) return result;
        
        solve(0, 0, "");
        
        return result;
    }
    
    public void solve(int start, int level, String ip) {
        if(level == 4 && start == input.length()) {
            result.add(ip.substring(0, ip.length() - 1));
            return;
        }
        if(level > 4 || start >= input.length()) return;
        
        if(input.charAt(start) == '0') {
            solve(start + 1, level + 1, ip + "0.");
        } else {
            for(int i = 1; i <= 3; i++){ 
                if(start + i > input.length()) continue;
                
                var substring = input.substring(start, start + i);
                
                if(Integer.parseInt(substring) <= 255) solve(start + i, level + 1, ip + substring + ".");
            }
        }
    }
}

제출 화면

오늘 내 submission 창을 보면 엄창나게 많은 wrong들을 볼 수 있는데 leetcode extension을 개발하느라 그랬다.

그래도 어느정도 가닥이 잡힌 것 같으니 더 다듬어서 배포하고 홍보를 해봐야겠다!

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