뒤죽박죽 코딩 이야기

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

제출 화면

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

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

2022년 12월 13일 화요일 - 이제는 자동화가 잘 붙었어!

오늘 올려볼 문제는 931번 Minimum Falling Path Sum 이라는 문제이다.

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

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

조금만 생각했다면 섹시하게 풀 수 있었을 텐데...

입력

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

풀이 및 코드

위 2차원 배열에서 세로로 합하면서 이었을 때 가장 작은 값이 무엇인지 구하는 문제이다.

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

그냥 뭐 딱봐도 dp로 풀면되는 문제이다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int c = matrix.length, r = matrix[0].length;
        for(int i = 1; i < c; i++) {
            for(int j = 0; j < r; j++) {
                int num = Integer.MAX_VALUE;
                for(int k = -1; k <= 1; k++) {
                    if(0 <= j + k && j + k < r) num = Math.min(num, matrix[i][j] + matrix[i - 1][j + k]);
                }
                matrix[i][j] = num;
            }
        }
        
        int result = matrix[c - 1][0];
        for(int i = 1; i < r; i++) result = Math.min(result, matrix[c - 1][i]);
        
        return result;
    }
}

제출 화면

오늘 edge case 때문에 코드가 조금 더러워졌는데 이를 Math.max나 Math.min을 사용하면 훨씬 예쁘게 짤 수 있었다...

다음에는 이런일이 있을 때 꼭 써먹어야겠다!

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

2022년 12월 12일 월요일 - 아니 왜 비가 오냐;;

오늘 올려볼 문제는 70번 Climbing Stairs 이라는 문제이다.

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

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

순간 이지인데 조금 어려워서 당황...

입력

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

풀이 및 코드

계단 개수가 n개인 계단을 1칸 또는 2칸씩 오른다고 했을 때 오를 수 있는 가짓수에 대한 것을 구하는 문제이다.

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

그냥 피보나치 수열하고 똑같다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        
        for(int i = 2; i <= n; i++) { 
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
}

제출 화면

처음에 피보나치를 생각하지 못하고 버벅대고 있다가 나중에 생각나서 후다닥 풀었다.

내일은 그냥 재밌는 문제 나왔으면 좋겠다.

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

2022년 12월 10일 토요일 - 와우 블로그 오랜만~~~~~

오늘 올려볼 문제는 1339번 Maximum Product of Splitted Binary Tree 이라는 문제이다.

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

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

맥에서 캡처하니 shottr 쓸 수 있는건 좋다 ㅎㅎ

입력

사진에서도 볼 수 있듯이 Binary Tree 하나가 입력으로 들어온다.

풀이 및 코드

주어진 트리를 2개의 서브트리로 분리하여 각 트리의 합을 곱했을 때 가장 큰 값이 되는 값을 구해서 10^9 + 7로 나눈 값을 리턴하는 문제이다.

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

dfs로 각 노드가 루트가 되는 서브트리가 되었을 때 그 서브트리의 합을 노드에다가 적어두고 전체 트리의 합을 구했다.

이후 bfs로 순회하면서 전체합에서 노드의 값을 뺀 값과 노드의 값을 곱해서 최대값을 찾는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    final int mod = 1000000007;
    long result = 0;
    int sum = 0;
    public int maxProduct(TreeNode root) {
        sum = setSum(root);
        
        var q = new LinkedList<TreeNode>();
        q.add(root);
        
        while(!q.isEmpty()) {
            var size = q.size();
            
            for(int i = 0; i < size; i++) {
                var now = q.poll();
                if(now == null) continue;
                
                result = Math.max(result, (long)now.val * (long)(sum - now.val));
                
                q.add(now.left);
                q.add(now.right);
            }
        }
        
        return (int)(result % mod);
    }
    
    public int setSum(TreeNode root) {
        if(root == null) return 0;
        
        root.val += setSum(root.left) + setSum(root.right);
        
        return root.val;
    }
}

제출 화면

이렇게 오랜만에 블로그를 쓰니깐 또 뭔가 느낌이 남다르다.

이제는 문서화를 열심히 하려고하다보니 집에 와서 할 게 더 늘은거 같지만 그래도 열심히 해야겠다.

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