뒤죽박죽 코딩 이야기

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여야 한다...

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

2023년 01월 05일 목요일 - 왜 체했지...

오늘 올려볼 문제는 452번 Minimum Number of Arrows to Burst Balloons 이라는 문제이다.

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

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

어려울거 같았는데 생각보다는 빨리 풀림

입력

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

풀이 및 코드

주어진 point 위치만큼 차지하고 있는 풍선들이 가로로 길게 있다. (세로 위치는 안중요함)

이 때 한 지점에서 화살을 세로로 날리면 그 지점에 겹쳐있는 풍선들은 모두 터진다.

이 때 모든 풍선을 터트리는 가장 적은 화살을 날리는 횟수를 구하는 문제이다.

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

정렬을 한 이후에 그리디로 문제를 풀면 될 것 같았다.

(가장 길이가 짧은 풍선이 맨 앞에 있다고 생각하면 쨋든 이 풍선들을 터뜨리긴 해야하니깐 이런 애들부터 터뜨린다라고 생각하면 조금 이해가 쉬우려나..?)

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> a[0] == b[0] ? (a[1] < b[1] ? -1 : 1) : (a[0] < b[0] ? -1 : 1));
        int result = 1, left = points[0][0], right = points[0][1];
        
        for(int i = 1; i < points.length; i++) {
            var p = points[i];
            if(right < p[0]) {
                result++;
                right = p[1];
            } else {
                left = p[0];
                right = Math.min(p[1], right);
            }
        }
        
        return result;
    }
}

제출 화면

이야 오늘 진짜 처음보는 경우가 있었는데 정렬 함수 사용할 때는 조심해야한다는 것이다.

아무 생각없이 람다로 (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]를 넘겼는데 여기서 - 연산 때문에 오버플로우가 날 수 있었다.

그래서 정렬을 했는데 정렬이 안되는 기이한 현상이 일어났다... ㅋㅋㅋㅋㅋㅋ

와 진짜 처음보는 경우라서 머리속에는 깊게 남을 것 같다 ㅋㅋㅋ

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

2023년 01월 04일 수요일 - 왜 아직도 수요일?

오늘 올려볼 문제는 2244번 Minimum Rounds to Complete All Tasks 이라는 문제이다.

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

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

3분컷!

입력

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

풀이 및 코드

입력으로 각 일의 level들이 들어온다. 일을 할 때는 무조건 같은 level의 일 2개 또는 3개씩 해야한다.

이 때 최소로 일하는 횟수를 구하는 문제이다. (못구하면 -1 리턴)

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

1개를 제외하고는 2를 더한다음에 3을 나눈 값이 해당 level에 있는 일을 하는 최소한의 횟수이다.

ex) 2 level 일이 8개 있으면 (8 + 2) / 3 => 3 즉 [3개, 3개, 2개] 이렇게 일을 처리하는 식으로

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minimumRounds(int[] tasks) {
        var map = new HashMap<Integer, Integer>();
        var result = 0;
        
        for(var task: tasks) map.put(task, map.getOrDefault(task, 0) + 1);
        
        for(var value: map.values()) {
            if(value == 1) return -1;
            result += (value + 2) / 3;
        }   
        
        return result;
    }
}

제출 화면

오늘은 생각보다 문제가 너무 쉬웠다.

내일은 좀 재미진 문제가 나왔으면 좋겠다.

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

2023년 01월 03일 화요일 - 어우 추워

오늘 올려볼 문제는 944번 Delete Columns to Make Sorted 이라는 문제이다.

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

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

이지하지요

입력

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

풀이 및 코드

String 배열의 열을 봤을 때 정렬되어있지 않은 열을 지운다고 할 때 지우는 열의 개수를 구하는 문제이다.

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

뭐 별거없이 이전 값 비교하는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minDeletionSize(String[] strs) {
        int result = 0;
        
        for(int i = 0; i < strs[0].length(); i++) {
            for(int j = 1; j < strs.length; j++) {
                if(strs[j].charAt(i) < strs[j - 1].charAt(i)) {
                    result++;
                    break;
                }
            }
        }
        
        return result;
    }
}

제출 화면

뭐 오늘은 너무 쉬워서 딱히 할말은 없당.

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