뒤죽박죽 코딩 이야기

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

제출 화면

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

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

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

2022년 10월 28일 금요일 - 오랜만이구만

오늘 올려볼 문제는 49번 Group Anagrams 이라는 문제이다.

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

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

생각을 더해서 어렵게 풀려고 했었다..

입력

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

풀이 및 코드

같은 anagram인 String들끼리 모아서 리스트로 리턴하는 문제다.

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

Char 배열을 기준으로 개수를 세주고 이를 HashMap의 키로 사용하는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        var countSet = new HashMap<String, ArrayList<String>>();
        
        for(var str: strs) {
            var keyArr = new char[26];
            
            for(var c : str.toCharArray()) keyArr[c - 'a']++;
            
            String key = new String(keyArr);
            
            if(!countSet.containsKey(key)) countSet.put(key, new ArrayList<>());
            
            countSet.get(key).add(str);
        }
        
        List<List<String>> result = new ArrayList<>();
        
        for(var keySet : countSet.entrySet()) result.add(keySet.getValue());
        
        return result;
    }
}

제출 화면

이제 꽤나 중요한 시기는 지나있는 상황이 됐다.

인생에서 한 번의 전환점이라 생각하고 열심히 살아야겠다!

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

2022년 10월 14일 금요일 - 금요일 조아!

오늘 올려볼 문제는 2095번 Delete the Middle Node of a Linked List 이라는 문제이다.

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

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

내일 화이팅합시다!!

입력

사진에서도 볼 수 있듯이 LinkedList의 head 노드가 입력으로 들어온다.

풀이 및 코드

해당 LinkedList의 중간 노드를 끊어서 리턴하는 문제다.

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

토끼와 거북이 알고리즘을 사용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if(head.next == null) return null;
        
        ListNode s = head, f = head, pre = null;
        
        while(true) {
            f = f.next;
            if(f == null) {
                pre.next = s.next;
                break;
            }
            
            f = f.next;
            if(f == null) {
                s.next = s.next.next;
                break;
            }
            
            pre = s;
            s = s.next;
        }
        
        return head;
    }
}

제출 화면

휴 이제 내일인데... 잘 할수 있을지 모르겠다....

쨌든 최선을 다해보자!!!

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

2022년 10월 12일 수요일 - 열심히 준비하자!!

오늘 올려볼 문제는 976번 Largest Perimeter Triangle 이라는 문제이다.

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

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

드디어 리팩토링 기간!! 너무 좋아!!

입력

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

풀이 및 코드

주어진 배열에서 3개의 원소를 골라 삼각형을 만들었을 때 둘레가 가장 긴 삼각형의 둘레를 구하는 문제이다.

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

정렬한 후에 뒤에서부터 삼각형이 가능한지 판단하고 삼각형이 가능하면 바로 리턴해줬다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        for(int i = nums.length - 3; i >= 0; i--) {
            if(nums[i] + nums[i + 1] > nums[i + 2]) return nums[i] + nums[i + 1] + nums[i + 2];
        }
        return 0;
    }
}

제출 화면

요즘 시기적으로 중요한 시기인데 힘내서 좋은 결과 얻었으면 좋겠다!

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

2022년 10월 04일 화요일 - 번아웃? 아닌가?

오늘 올려볼 문제는 112번 Path Sum 이라는 문제이다.

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

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

뭔가 요즘 열심히는 사는데 뭘 위한건지 잘 모르겠다

입력

사진에서도 볼 수 있듯이 Binaray Tree의 Root Node가 입력으로 들어온다.

풀이 및 코드

Leaf 노드까지 합을 구했을 때 targetSum을 만들 수 있는 path가 있는지 판단하는 문제댜.

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

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

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()) {
            int size = q.size();
            
            for(int i = 0; i < size; i++) {
                TreeNode now = q.poll();
                
                if(isLeaf(now) && now.val == targetSum) return true;
                
                if(now.left != null) {
                    now.left.val += now.val;
                    q.add(now.left);
                }
                
                if(now.right != null) {
                    now.right.val += now.val;
                    q.add(now.right);
                }
            }
        }
        
        return false;
    }
    
    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }
}

제출 화면

음.. 뭐랄까 진로가 정해진게 얼마 안됐으니 잘 모르는게 많은게 당연하지만.. 그 사이 간격을 빠르게 좁히고 싶은 마음이 큰 시기인거 같다.

그런 의미에서 오늘은 천천히 쉬어가는 날인걸로.

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