뒤죽박죽 코딩 이야기

2023년 02월 06일 월요일 - 보드게임 개꿀잼~~

오늘 올려볼 문제는 1470번 Shuffle the Array 이라는 문제이다.

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

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

이지하지만.. space(1)로는 좀 어렵긴 해

입력

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

풀이 및 코드

앞에 n개 원소와 뒤에 n개 원소를 하나씩 섞는 문제이다.

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

그냥 뭐... 넣어주기만 하며되는 문제...

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[] shuffle(int[] nums, int n) {
        var result = new int[2 * n];
        
        for(int i = 0; i < n; i++) {
            result[i * 2] = nums[i];
            result[i * 2 + 1] = nums[n + i];
        }
        
        return result;
    }
}

제출 화면

사실 space O(1)로 풀려고 했지만 못풀었는데... 방법이 있긴 했다...

하지만 뭐 고민했어도 못풀었을것 같아서 아쉽진 않다!

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

2023년 02월 05일 일요일 - 주말은 너무 빠르다...

오늘 올려볼 문제는 438번 Find All Anagrams in a String 이라는 문제이다.

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

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

오늘도 풀었던 문제네?

입력

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

풀이 및 코드

p의 anagram이 s의 substring으로 포함하고 있으면 해당 substring들의 모든 시작 index를 구하는 문제이다.

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

오늘도 그저 윈도우 슬라이드만 사용하면 문제가 풀린다...

이제 코드를 봐보자!

풀이코드

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        var result = new ArrayList<Integer>();
        if(s.length() < p.length()) return result;
        
        var arr = new int[26];
        int n = p.length(), sum = n;
        
        for(var c : p.toCharArray()) arr[c - 'a']++;
        
        for(int i = 0; i < n; i++) if(arr[s.charAt(i) - 'a']-- > 0) sum--;
        
        if(sum == 0) result.add(0);
        
        for(int i = n; i < s.length(); i++) {
            if(arr[s.charAt(i) - 'a']-- > 0) sum--;
            if(++arr[s.charAt(i - n) - 'a'] > 0) sum++;
            if(sum == 0) result.add(i - n + 1);
        }
        
        return result;
    }
}

제출 화면

갑자기 풀었었던 문제가 많이 나오네..?

내가 문제를 많이 푼건지 아니면 리트코드가 조금 중복해서 내는건지..?

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

2023년 02월 04일 토요일 - T1!

오늘 올려볼 문제는 567번 Permutation in String 이라는 문제이다.

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

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

이것도 풀었던 문제구만

입력

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

풀이 및 코드

s1의 permutation이 s2의 substring으로 들어가있는지 판단하는 문제이다.

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

그저 윈도우 슬라이드면 충분하다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if(s1.length() > s2.length()) return false;
        
        var arr = new int[26];
        int n = s1.length(), sum = n;
        
        for(var c : s1.toCharArray()) arr[c - 'a']++;
        
        for(int i = 0; i < n; i++) if(arr[s2.charAt(i) - 'a']-- > 0) sum--;
        
        if(sum == 0) return true;
        
        for(int i = n; i< s2.length(); i++) {
            if(arr[s2.charAt(i) - 'a']-- > 0) sum--;
            if(++arr[s2.charAt(i - n) - 'a'] > 0) sum++;
            if(sum == 0) return true;
        }
            
        return false;
    }
}

제출 화면

뭐 이정도는 easy하죠~

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

2023년 02월 03일 금요일 - 너무 많이 잃었다...

오늘 올려볼 문제는 6번 Zigzag Conversion 이라는 문제이다.

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

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

블랙잭 꿀잼이지만 너무 많이 잃음 ㅠㅠ

입력

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

풀이 및 코드

numRows 폭을 가지는 지그재그 String을 만들었을 때 맨 위 row부터 차례대로 읽었을 때 나오는 String을 구하는 문제이다.

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

row를 key 그리고 해당 row의 String을 value라고 생각해서 StringBuilder 배열을 만들어줬고 이를 나중에 한 번에 합쳐주는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public String convert(String s, int numRows) {
        if(numRows == 1) return s;
        
        var arr = new StringBuilder[numRows + 1];
        for(int i = 0; i <= numRows; i++) arr[i] = new StringBuilder();
        int index = 1, dir = -1;
        
        for(var c: s.toCharArray()) {
            if(index == 1 || index == numRows) dir *= -1;
            arr[index].append(c);
            index += dir;
        }
        
        for(int i = 1; i <= numRows; i++) arr[0].append(arr[i].toString());
        
        return arr[0].toString();
    }
}

제출 화면

오늘 블랙잭 재미있게 쳤지만 많이 잃었다 ㅠㅠ

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

2023년 02월 02일 목요일 - 아쉽다 ㅠㅠ

오늘 올려볼 문제는 953번 Verifying an Alien Dictionary 이라는 문제이다.

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

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

또 너냐 킹겐....

입력

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

풀이 및 코드

order로 들어온 순서가 새로운 알파벳 순서라고 했을 때 words가 정렬되어있는지 판단하는 문제이다.

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

그냥... int 배열로 순서를 저장하고 단순비교로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        var arr = new int[26];
        
        for(int i = 0; i < 26; i++) arr[order.charAt(i) - 'a'] = i;
        
        Loop:
        for(int i = 1; i < words.length; i++) {
            var ps = words[i - 1];
            var ns = words[i];
            for(int j = 0; j < Math.min(ps.length(), ns.length()); j++) {
                if(arr[ps.charAt(j) - 'a'] > arr[ns.charAt(j) - 'a']) return false;
                else if(arr[ps.charAt(j) - 'a'] == arr[ns.charAt(j) - 'a']) continue;
                else continue Loop;
            }
            if(ps.length() > ns.length()) return false;
        }
        
        return true;
    }
}

제출 화면

아... T1의 첫 패배... 아쉽지만... 다음에 잘하면 된다!

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

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시가 되었다..

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

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