뒤죽박죽 코딩 이야기

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

제출 화면

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

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

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

제출 화면

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

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