뒤죽박죽 코딩 이야기

2023년 01월 20일 금요일 - 어우 연휴 너무 조아!!!!

오늘 올려볼 문제는 491번 Non-decreasing Subsequences 이라는 문제이다.

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

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

생각보다는 어려워잉...

입력

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

풀이 및 코드

배열의 subsequnce를 구하는데 해당 subsequnce는 오름차순으로 정렬되어있어야한다. 또한 subsequnce는 unique 해야한다.

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

입력의 크기가 작다보니 브루트포스, 백트래킹 같았다.

unique 함을 처리해야하는데 오름차순인게 주어졌으니 스택과 마지막에 스택에 넣은 값을 기준으로 백트래킹을 진행했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    int[] arr;
    public List<List<Integer>> findSubsequences(int[] nums) {
        arr = nums;
        
        solve(0, -10000, new Stack<>());
        
        return result;
    }
    
    public void solve(int index, int prev, Stack<Integer> s) {
        if(index == arr.length) {
            if(s.size() > 1) result.add(new ArrayList(s));
            return;
        }
        
        if(prev <= arr[index]) {
            s.push(arr[index]);
            solve(index + 1, arr[index], s);
            s.pop();
        }
        if(prev != arr[index]) solve(index + 1, prev, s);
    }
}

제출 화면

요즘 리트코드가 할만해보이는데 어려운 문제를 자꾸 낸다...

조금만 더 쉽게 내줬으면 ㅠ

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

2023년 01월 17일 화요일 - 아니 개 추워!!!!!

오늘 올려볼 문제는 926번 Flip String to Monotone Increasing 이라는 문제이다.

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

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

간단해보였지만 생각보다는 오래걸렸다..

입력

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

풀이 및 코드

Monotone Increasing한 String으로 만들기 위해서 각 원소를 뒤집으라는 문제다.

Monotone Increasing을 찾아봐도 잘 모르겠지만 대충 지수적으로 늘어나는 느낌인 것 같다.

여기서는 "0000", "0001", "0011", "0111", "1111" 처럼 아예 0이나 1로 이루어져 있거나 뒤에가 1로 채워져 있는 상태를 말한다.

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

일단 0개수 1개수를 세고 String을 순회한다.

0이 나오면 지나가고 1이 나오면 앞으로 남은 것들 중에 어떤 숫자를 뒤집어야지 작은게 나오는지 계산한다.

이렇게 최소값을 찾아나가는 방향으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        var oneZero = new int[2];
        
        for(int i = 0; i < n; i++) oneZero[s.charAt(i) == '1' ? 1 : 0]++;

        int result = Math.min(oneZero[0], oneZero[1]), flipedOnes = 0;
        
        for(int i = 0; i < n; i++) {
            oneZero[s.charAt(i) == '1' ? 1 : 0]--;
            
            if(s.charAt(i) == '0') continue;
            
            result = Math.min(result, flipedOnes++ + Math.min(oneZero[0], oneZero[1] + 1));
        }
        
        return result;
    }
}

제출 화면

저기서 0개수 1개수를 세지않고 그냥 순회 한 번 더 하려고 했었다가 TLE 떠서 개수 기억하게끔 후다닥 바꿨다.

간단해보이지만 생각보다 어려운 것 같다.

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

2023년 01월 16일 월요일 - 왜 월요일?

오늘 올려볼 문제는 57번 Insert Interval 이라는 문제이다.

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

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

오늘 너무 춥던데...

입력

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

풀이 및 코드

기존 간격들이 있고 새로운 간격이 하나 들어온다고 했을 때 겹치는 부분들을 합치는 문제이다.

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

이미 기존 간격들은 정력되어 있으니 newInterval을 적당한 위치에 넣고 머지하는 식으로 진행했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals.length == 0) return new int[][] {newInterval};
        
        var list = new ArrayList<int[]>();
        var temp = new ArrayList<int[]>();
        
        for(var itv: intervals) list.add(itv);
        
        for(int i = intervals.length - 1; i >= 0; i--) {
            if(list.get(i)[0] <= newInterval[0]) {
                list.add(i + 1, newInterval);
                break;
            }
        }
        
        if(list.size() == intervals.length) list.add(0, newInterval);
        
        
        int index = 0;
        temp.add(list.get(0));
        for(int i = 1; i < list.size(); i++) {
            var prev = temp.get(index);
            var now = list.get(i);
            
            if(prev[1] < now[0]) {
                temp.add(now);
                index++;
            } else {
                prev[0] = Math.min(prev[0], now[0]);
                prev[1] = Math.max(prev[1], now[1]);
            }
        }
        
        var result = new int[temp.size()][2];
        for(int i = 0; i < temp.size(); i++) result[i] = temp.get(i);
        
        return result;
    }
}

제출 화면

오늘은 너무 추웠다...

그 잠시 따뜻해졌다고 이 날씨가 춥다니... 인간은 적응의 동물이 맞나보다....

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

2023년 01월 14일 토요일 - 헤롱헤롱

오늘 올려볼 문제는 1061번 Lexicographically Smallest Equivalent String 이라는 문제이다.

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

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

어으 낮부터 술을 좀 마셨더니 머리가 아프구만

입력

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

풀이 및 코드

s1과 s2의 각 원소들끼리 대치가 가능하다고 한다.

abc와 def가 있다고 하면 a는 d랑 동일한 그룹에 포함되고 이 그룹안에서는 어떤 것이든 동등하다고 한다.

이렇게 그룹이 있다고 했을 때 baseStr을 사전적으로 가장 빠른 순서가 되게끔 바꾸어 구하는 것이 이 문제다.

조금 헤매다가 정답을 생각해냈다.

결국에 그룹을 만든다고 생각하면 Union Find를 사용하는게 가장 편했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    int[] arr = new int[26];
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        for(int i = 0; i < arr.length; i++) arr[i] = i;
        
        for(int i = 0; i < s1.length(); i++) {
            int c1 = find(s1.charAt(i) - 'a'), c2 = find(s2.charAt(i) - 'a');
            
            if(c1 == c2) continue;
            
            arr[Math.max(c1, c2)] = Math.min(c1, c2);
        }
        
        var sb = new StringBuilder();
        for(var c : baseStr.toCharArray()) sb.append((char)('a' + find(c - 'a')));
        
        return sb.toString();
    }
    
    public int find(int num) {
        if(arr[num] == num) return num;
        else return  arr[num] = find(arr[num]);
    }
}

제출 화면

어우 뭔가 오랜만에 블로그를 쓰는 것 같은데 그건 제 실력이 모자라서입니다...

최근 문제들이 다 어려웠어잉..

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

2023년 01월 11일 수요일 - 오늘은 어려운 문제 푸는 날인가?

오늘 올려볼 문제는 1443번 Minimum Time to Collect All Apples in a Tree 이라는 문제이다.

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

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

아니 이거 어려워!! 왜 미디엄이야!!!

입력

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

풀이 및 코드

0번 노드에서 출발하여 모든 사과를 따서 0번 노드로 다시 가져온다고 할 때 가장 적게 움직이는 길이가 무엇인지 구하는 문제이다.

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

조금 어려웠는데 dp를 어느정도 사용한 것 같다.

먼저 주어진 edges를 기준으로 hashmap에 트리를 구현한다.

이 후 사과가 열린 곳부터 0번 노드까지 dfs를 한다. 이 dfs를 하면서 길이를 잰다.

만약 0번 노드까지 가거나, 이전에 한 번 갔던 노드(이번 dfs에서 탐색한길 말고, 이전 dfs를 통해 사과를 따고 갔던 길)에 도착하면 해당 길이를 리턴한다. (이외는 음수 리턴)

(처음으로 이전에 한 번 갔던 노드가 결국에 다른 사과가 있던 곳과 가장 가까운 공통 조상이므로 해당 거리만 구하면 된다.)

음수가 아니라면 2배를 곱해서 result에 더한다.

이제 코드를 봐보자!

풀이코드

class Solution {
    boolean[] v;
    boolean[] visit;
    HashMap<Integer, ArrayList<Integer>> map;
    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        map = new HashMap<>();
        v = new boolean[n];
        visit = new boolean[n];
        
        for(var e : edges) {
            if(!map.containsKey(e[0])) map.put(e[0], new ArrayList<>());
            if(!map.containsKey(e[1])) map.put(e[1], new ArrayList<>());
            
            map.get(e[0]).add(e[1]);
            map.get(e[1]).add(e[0]);
        }
        v[0] = true;
        
        int result = 0;
        
        for(int i = 0; i < n; i++) {
            var apple = hasApple.get(i);
            
            if(!apple) continue;
            
            int length = dfs(i, 0);
            v[i] = true;
            
            if(length > 0) result += length * 2;
        }
        
        return result;
    }
    
    public int dfs(int root, int length) {
        if(v[root]) return length;
        if(visit[root]) return -1;
        
        visit[root] = true;
        
        for(var child: map.get(root)) {
            var l = dfs(child, length + 1);
            if(l > 0) {
                v[child] = true;
                visit[root] = false;
                return l;
            }
        }
        
        visit[root] = false;
        
        return -1;
    }
}

제출 화면

어후 첨 봤을 때는 어떻게 풀어야하나 막막했는데 시작점을 0이 아닌 사과가 있는 곳부터하니까 수월하게 풀렸다.

또 오늘은 오랜만에 표준입출력 사용하는 문제도 풀어봤는데 2시간 넘게 풀면서 오랜만에 옛날 느낌도 나서 좋았다.

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

2023년 01월 09일 월요일 - 으악 월욜

오늘 올려볼 문제는 144번 Binary Tree Preorder Traversal 이라는 문제이다.

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

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

preorder가 뭔지 기억이 안나서....허허

입력

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

풀이 및 코드

입력으로 받은 트리를 preorder로 순회하여 리턴하는 문제다.

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

dfs 한 단어로 정리할 수 있겠다.

이제 코드를 봐보자!

풀이코드

class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        dfs(root);
        return result;
    }
    
    public void dfs(TreeNode root) {
        if(root == null) return;
        result.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }
}

제출 화면

leetcode도 중복되는 문제가 많은 것 같다.

풀어본 문제 같은데 안 푼걸 보니....

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

2023년 01월 07일 토요일 - 자비로운 리트코드..

오늘 올려볼 문제는 134번 Gas Station 이라는 문제이다.

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

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

너무 안좋게 풀었지만 일단 풀었으니...

입력

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

풀이 및 코드

주유소가 있고 해당 주유소만큼 가는데 들어가는 비용이 있다.

이 때 한 주유소에서 시계방향으로 모든 주유소를 돈다고 할 때 모든 주유소를 들를 수 있는 위치를 구하는 문제이다.

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

가스와 비용의 차이를 구해서 이를 pq에 넣고 가스가 더 많이 남는 곳부터 일일히 탐색했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        var pq = new PriorityQueue<Point>((a, b) -> b.sum - a.sum);
        
        for(int i = 0; i < n; i++) {
            if(gas[i] - cost[i] >= 0) pq.add(new Point(i, gas[i] - cost[i]));
        }
        
        while(!pq.isEmpty()){
            int index = pq.poll().index;
            int sum = gas[index];

            for(int i = 0; i < n; i++) {
                sum -= cost[(index + i) % n];
                if(sum < 0) break;
                sum += gas[(index + i + 1) % n];
            }

            if(sum >= 0) return index;
        }
        
        return -1;
    }
    
    class Point{
        int index, sum;
        
        public Point(int index, int sum) {
            this.index = index;
            this.sum = sum;
        }
    }
}

제출 화면

오늘 나는 O(N^2)에 풀었지만 O(N)에 풀 수 있는 답이 있었다...

그걸보고 오늘 블로그를 쓸까말까 고민을 많이 했지만 일단 풀었으니... 올리긴 한다....

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

2023년 01월 06일 금요일 - 황금같은 금요일!

오늘 올려볼 문제는 1833번 Maximum Ice Cream Bars 이라는 문제이다.

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

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

이렇게 쉬운데 왜 미디엄이지...?

입력

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

풀이 및 코드

coins로 아이스크림을 사먹을 때 가장 많이 사먹을 수 있는 개수를 구하는 문제이다.

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

정렬 후 그리디를 사용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        
        for(int i = 0; i < costs.length; i++) {
            coins -= costs[i];
            if(coins < 0) return i;
        }
        
        return costs.length;
    }
}

제출 화면

솔직히 오늘 문제 easy여야 한다...

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