뒤죽박죽 코딩 이야기

2023년 02월 09일 목요일 - 오늘 금욜 아니었나..?

오늘 올려볼 문제는 2306번 Naming a Company 이라는 문제이다.

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

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

하드치고는 1트 클

입력

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

풀이 및 코드

1. 두 개의 단어를 고른다.
2. 두 개의 단어의 맨 앞글자를 서로 바꾼다.
3. 바꾼 단어가 ideas 배열에 둘 다 존재하지 않는다면 valid한 이름이다. (순서 상관있음)
4. 이외에는 invalid하다

이 규칙을 따르는 valid한 이름의 개수를 구하는 문제이다.

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

맨 앞글자만 서로 바꾸는 것이므로 HashSet 배열을 만들고 맨 앞글자를 index로 해서 뒤에 String 부분을 set에 저장했다.

이 후 모든 쌍에 대해서 교집합만큼 뺀 이후 곱해주고 2를 곱해주면 내가 원하는 값을 찾아낼 수 있었고 이런식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public long distinctNames(String[] ideas) {
        var arr = new HashSet[26];
        
        for(int i = 0; i < arr.length; i++) arr[i] = new HashSet<String>();
        
        for(var idea : ideas) arr[idea.charAt(0) - 'a'].add(idea.substring(1));
        
        long result = 0;
        
        for(int i = 0; i < arr.length - 1; i++) {
            for(int j = i + 1; j < arr.length; j++) {
                var set = new HashSet<String>();
                set.addAll(arr[i]);
                
                set.retainAll(arr[j]);
                int retainCnt = set.size();
                
                result += 2 * (arr[i].size() - retainCnt) * (arr[j].size() - retainCnt);
            }
        }
        
        return result;
    }
}

제출 화면

hard 문제인 것 치고는 너무 쉽게 풀어서 놀랐다.

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

2023년 02월 08일 수요일 - T1!

오늘 올려볼 문제는 45번 Jump Game II 이라는 문제이다.

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

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

아 생각보다 잘 못 풀어서 아쉽

입력

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

풀이 및 코드

각 원소에 있는 수의 길이를 최대로 점프할 수 있다고 할 때 배열의 끝까지 가장 적은 점프로 갈 수 있는 점프수를 구하는 문제이다.

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

dp를 사용하고 count를 저장하는데 최대로 점프뛸 수 있는곳에 이미 저장한 값이 있으면 넘어가고 없다면 해당 길이까지 모두 dp를 채워가는 식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        var arr = new int[n];
        
        if(n == 1) return 0;
        
        for(int i = 0; i < n; i++) {
            if(i + nums[i] >= n - 1) return arr[i] + 1;
            
            for(int j = i + 1; j <= i + nums[i]; j++) {
                if(arr[j] > arr[i] || arr[j] == 0) arr[j] = arr[i] + 1;
            }
        }
        
        return 0;
    }
}

제출 화면

discuss를 보니 훨씬 간단하면서 멋있고 섹시한 코드가 있었다.

이런 코드들을 잘 기억해두고 나중에 응요해봐야겠다.

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

2023년 02월 07일 화요일 - 야근시러

오늘 올려볼 문제는 904번 Fruit Into Baskets 이라는 문제이다.

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

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

문제 좀더 깔쌈하게 풀 수 있었는데 ㄲㅂ

입력

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

풀이 및 코드

과일을 따기 시작하면 계속 따야한다.

한 바구니에는 한 종류의 과일만 넣어야하며 바구니는 2개가 있다.

가장 많은 과일을 담을 수 있는 경우의 수를 구하는 문제이다.

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

오늘도 윈도우 슬라이딩....

이제 코드를 봐보자!

풀이코드

class Solution {
    public int totalFruit(int[] fruits) {
        int result = 0, diff = 0, index = 0, length = 0;
        var map = new HashMap<Integer, Integer>();
        
        for(var f : fruits) {
            map.put(f, map.getOrDefault(f, 0) + 1);
            if(map.get(f) == 1) diff++;
            length++;
            
            while(diff > 2) {
                map.put(fruits[index], map.get(fruits[index]) - 1);
                if(map.get(fruits[index++]) == 0) diff--;
                length--;
            }
            
            result = Math.max(result, length);
        }
        
        return result;
    }
}

제출 화면

사실 diff 변수를 안쓰고 hashmap의 size를 사용하는게 더 좋아보이긴 했다.

나중에는 좀 더 신경쓰면서 푸는걸로!

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

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의 첫 패배... 아쉽지만... 다음에 잘하면 된다!

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