뒤죽박죽 코딩 이야기

2023년 01월 02일 월요일 - 아니 왜 아직 월요일?

오늘 올려볼 문제는 520번 Detect Capital 이라는 문제이다.

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

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

regex가 느리긴 느려..

입력

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

풀이 및 코드

다음 3가지 규칙 중 하나라도 맞는지 판단하는 문제이다.

1. 모두 대문자로 이루어져있는가
2. 모두 소문자로 이루어져있는가
3. 첫번째 글자만 대문자고 다른 문자는 모두 소문자로 이루어져있는가

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

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

이제 코드를 봐보자!

풀이코드

import java.util.regex.Pattern;

class Solution {
    public boolean detectCapitalUse(String word) {
        return Pattern.matches("[A-Z]+", word) || Pattern.matches("[a-z]+", word) || Pattern.matches("[A-Z][a-z]+", word);
    }
}

제출 화면

옛날에 일일히 비교하면서 푼 코드도 있는데 그게 훨씬 빠르긴하다.

확실히 regex가 편리하긴하지만 느리긴하다..

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

2023년 01월 01일 일요일 - Hello 2023!

오늘 올려볼 문제는 290번 Word Pattern 이라는 문제이다.

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

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

23년이 왔다니... 실감이 안나는구만

입력

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

풀이 및 코드

pattern에 맞게끔 s가 구성되어있는지 판단하는 문제이다.

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

HashMap을 사용해서 key value 방식으로 저장하고 중복되는 키를 사용하는지 set을 사용하여 판단하는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean wordPattern(String pattern, String s) {
        var map = new HashMap<Character, String>();
        var set = new HashSet<String>();
        var patterns = pattern.toCharArray();
        var arr = s.split(" ");
        
        if(patterns.length != arr.length) return false;
        
        for(int i = 0; i < patterns.length; i++) {
            var c = patterns[i];
            if(map.containsKey(c)) {
                if(!map.get(c).equals(arr[i])) return false;
            } else {
                if(set.contains(arr[i])) return false;
                map.put(c, arr[i]);
                set.add(arr[i]);
            }
        }
        
        return true;
    }
}

제출 화면

옛날에 풀었던 문제길래 submission을 봤는데 엄청나게 많이 틀렸었다..

대체 왜 이렇게 많이 틀렸는지 풀면서 확인했는데 이 문제가 leetcode치고 edge case가 좀 있는 문제라서 그랬다 ㅋㅋㅋ

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

2022년 12월 30일 금요일 - 22년이 끝나간다....

오늘 올려볼 문제는 797번 All Paths From Source to Target 이라는 문제이다.

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

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

생각보다는 쉽게 풀렸당

입력

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

풀이 및 코드

주어진 DAG에서 0부터 n-1 노드까지 갈 수 있는 방법들을 구해서 리턴하는 문제이다.

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

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

이제 코드를 봐보자!

풀이코드

class Solution {
    int n;
    int[][] g;
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        g = graph;
        n = g.length;
        solve(0, new Stack<Integer>());
        return result;
    }
    
    public void solve(int index, Stack<Integer> s) {
        s.push(index);
        
        if(index == n - 1) {
            result.add(new ArrayList<Integer>(s));
            s.pop();
            return;
        }
        
        for(var num: g[index]) {
            solve(num, s);
        }
        
        s.pop();
    }
}

제출 화면

이제 하루하고 몇시간 뒤면 2023년이 된다는게 신기하다....

안녕~

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

2022년 12월 27일 화요일 - 3일만에 출근... 힘드러...

오늘 올려볼 문제는 2279번 Maximum Bags With Full Capacity of Rocks 이라는 문제이다.

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

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

생각해보니 더 효율적으로 짤 수 있었다

입력

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

풀이 및 코드

주어진 가방들에 돌을 담을 수 있는 개수와 돌이 담겨져 있는 개수가 있다.

이 때 추가적인 돌 n개가 있을 때 이를 배분하여 담았을 때 가장 많은 꽉 채워진 가방을 구하라는 문제이다.

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

가방의 용량과 가방에 든 돌의 개수의 차이를 구하여 차이가 작은 것부터 채워나가는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        var pq = new PriorityQueue<Integer>();
        int result = 0;
        
        for(int i = 0; i < rocks.length; i++) pq.add(capacity[i] - rocks[i]);
        
        while(!pq.isEmpty()) {
            additionalRocks -= pq.poll();
            
            if(additionalRocks < 0) break;
            result++;
        }
        
        return result;
    }
}

제출 화면

생각해보니 그냥 pq를 사용하지 않고 정렬 한 번 하는게 훨씬 더 효율적이었을 것이다.

하지만 처음 푼건 이렇게 푼 것이므로... 머리에 잘 기억해두는 것으로 만족해야겠다.

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

2022년 12월 26일 월요일 - 쿠리수마수 파티는 역시 다음날에 해야지~

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

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

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

2분컷!

입력

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

풀이 및 코드

각 원소에 적혀있는 수만큼 최대로 점프할 수 있다고 할 때 마지막 인덱스까지 갈 수 있는지 여부를 구하는 문제이다.

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

항상 점프는 1칸씩만하면서 더 멀리 뛸 수 있는 수로 갈아끼워서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean canJump(int[] nums) {
        int jump = nums[0];
        
        for(int i = 1; i < nums.length; i++) {
            if(jump == 0) return false;
            jump = Math.max(--jump, nums[i]);
        }
        
        return true;
    }
}

제출 화면

오늘은 문제를 빨리 풀어서 뭔가 기분이 좋았다. ㅋㅋㅋㅋ

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

2022년 12월 25일 일요일 - 메리 크리스마스~~

오늘 올려볼 문제는 2389번 Longest Subsequence With Limited Sum 이라는 문제이다.

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

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

이진 탐색 변형을 익힌다고 생각보다 오래걸렸음..

입력

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

풀이 및 코드

nums의 subsequence 중에 합이 queries[i] 보다 같거나 작은 subsequence 중 가장 긴 길이를 구해서 배열로 리턴하는 문제이다.

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

nums를 정렬하고 그 index까지의 합을 구해서 저장한다. ex) nums = {1,2,3,4} -> {1,3,6,10}

이후 이진 탐색을 통해서 queries[i]보다 같거나 작은 값을 nums에서 이진 탐색으로 찾는다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        var result = new int[queries.length];
        
        Arrays.sort(nums);
        
        for(int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
        
        for(int i = 0; i < result.length; i++) {            
            result[i] = find(nums, queries[i]);
        }
        
        return result;
    }
    
    public int find(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
}

제출 화면

이진 탐색 변형에 좀 약한걸 알고있었어서 익힐겸 고민을 좀 했더니 이지문제에 생각보다 많은 시간을 썼다.

하지만 충분히 익힌 것 같으니 도움이 된 것 같다!

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

2022년 12월 18일 일요일 - 재벌집 막내아들 재밌네요 ㅎㅎ

오늘 올려볼 문제는 739번 Daily Temperatures 이라는 문제이다.

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

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

한 번 풀었었던 문제인데 소름돋게 똑같이 풀었다...

입력

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

풀이 및 코드

온도들이 입력으로 들어오는데 해당 온도보다 더 높은 온도가 며칠뒤에 오는지 구하여 리턴하는 문제이다.

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

스택에 index를 저장하고 온도가 더 커지는 순간 index끼리 비교하여 배열에 넣어주면 된다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> s = new Stack<>();
        
        for(int i = 0; i < temperatures.length; i++) {
            while(!s.isEmpty() && temperatures[s.peek()] < temperatures[i]) {
                temperatures[s.peek()] = i - s.pop();
            }
            s.push(i);
        }
        
        while(!s.isEmpty()) temperatures[s.pop()] = 0;
        
        return temperatures;
    }
}

제출 화면

뭔가 이상해서 submission을 열어봤는데 이미 풀었었던 문제였다.

그래서 어떻게 풀었나 확인했는데 진짜 소름돋게 비슷하게 풀었었다 ㅋㅋㅋㅋ

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

2022년 12월 17일 토요일 - 완차이 너무 마시땅!

오늘 올려볼 문제는 150번 Evaluate Reverse Polish Notation 이라는 문제이다.

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

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

이게 되나하고 제출했는데 이게 되네?

입력

사진에서도 볼 수 있듯이 정수 또는 +, -, *, / 로 이루어져있는 String 배열 1개가 입력으로 들어온다.

풀이 및 코드

주어진 String 배열이 후위계산식일 때 해당 식을 계산하는 문제이다.

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

스택에 숫자를 넣어가면서 연산자가 나왔을 때 스택에서 숫자를 빼서 계산한 후 다시 스택에 넣어주는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> s = new Stack<>();
        
        for(var t : tokens) {
            if(t.equals("+")) {
                int n = s.pop();
                s.push(s.pop() + n);
            } else if(t.equals("-")) {
                int n = s.pop();
                s.push(s.pop() - n);
            } else if(t.equals("*")) {
                int n = s.pop();
                s.push(s.pop() * n);
            } else if(t.equals("/")) {
                int n = s.pop();
                s.push(s.pop() / n);
            } else {
                s.push(Integer.parseInt(t));
            }
        }
        
        return s.pop();
    }
}

제출 화면

후위계산 방법에 대해서 배운지 오래돼서 어쩌면 검색을 해야하겠는데~~ 생각을 했었는데 그냥 풀려버려서 조금 당황했다 ㅋㅋㅋㅋ

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