뒤죽박죽 코딩 이야기

2023년 02월 25일 토요일 - 최강 T1!!

오늘 올려볼 문제는 121번 Best Time to Buy and Sell Stock 이라는 문제이다.

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

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

이것도 풀었었던 문제네

입력

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

풀이 및 코드

주어진 주식 차트 가장 큰 수익을 만들었을 때 그 수익을 구하는 문제이다.

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

뭐 그냥 순회하면서 찾으면 되는....

이제 코드를 봐보자!

풀이코드

class Solution {
    public int maxProfit(int[] prices) {
        int min = prices[0], result = 0;
        for(var p : prices) {
            min = Math.min(min, p);
            result = Math.max(result, p - min);
        }
        
        return result < 0 ? 0 : result;
    }
}

제출 화면

역시 티원이 최강이다!!!

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

2023년 02월 23일 목요일 - 대황T1!

오늘 올려볼 문제는 502번 IPO 이라는 문제이다.

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

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

크으 티원 경기력 미쳤다리

입력

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

풀이 및 코드

문제 설명하기에는 조금 어렵다... 사진 참고해주세요...

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

TreeMap으로 key-value 형식으로 저장해준다.

이 후 floorKey를 사용해서 최대 이익을 뽑아내고 그리디를 사용하는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        var map = new TreeMap<Integer, ArrayList<Integer>>();
        
        for(int i = 0; i < profits.length; i++) {
            if(!map.containsKey(capital[i])) map.put(capital[i], new ArrayList<>());
            map.get(capital[i]).add(profits[i]);
        }
        
        var pq = new PriorityQueue<Integer>(Collections.reverseOrder());
        int result = w;
        
        for(int i = 0; i < k; i++) {
            while(map.floorKey(result) != null) {
                pq.addAll(map.get(map.floorKey(result)));
                map.remove(map.floorKey(result));
            }
            
            if(!pq.isEmpty()) result += pq.poll();
        }
        
        return result;
    }
}

제출 화면

pq 2개로 문제를 풀 수 있었다... ㄷㄷ

아 그리고 어제 감성 글은 안썼다.

왜냐고? 까먹었거든 ㅋ

오늘 쓸 듯

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

2023년 02월 22일 수요일 - 민규 자취방에 놀러가따!

오늘 올려볼 문제는 1011번 Capacity To Ship Packages Within D Days 이라는 문제이다.

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

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

이진탐색 파뤼

입력

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

풀이 및 코드

int 배열 순서를 지키면서 배를 통해 물건을 나를 때 days 만큼 나를 수 있다. 모든 물건을 나르는데 필요한 배의 가장 작은 수용량을 구하는 문제이다.

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

배 용량으로 바이너리 서치를 하면 된다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int sum = 0, max = 0;
        for(var w : weights) {
            sum += w;
            max = Math.max(max, w);
        }
        
        int left = max, right = sum;
        
        while(left <= right) {
            int count = 0, s = 0, mid = left + (right - left) / 2;
            
            for(var w : weights) {
                if(s + w > mid) {
                    s = 0;
                    count++;
                }
                
                s += w;
            }
            
            if(count >= days) left = mid + 1;
            else right = mid - 1;
        }
        
        return left;
    }
}

제출 화면

오늘은 블로그로 갬성 글을 조금 써볼 생각이다.

왜냐고? 그냥

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

2023년 02월 21일 화요일 - 스키 여행 너무 재밌었다!

오늘 올려볼 문제는 540번 Single Element in a Sorted Array 이라는 문제이다.

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

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

최근 이지 문제는 귀찮아서 안올렸더니 굉장히 오랜만에 쓰는 것 같네요

입력

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

풀이 및 코드

정렬된 배열이 들어오는 데 이 배열에 정확히 1개의 숫자만 1개 존재하고 나머지 숫자들은 2개 존재한다.

이 때 시간 복잡도 O(log n) 공간 복잡도 O(1)로 1개 있는 숫자를 찾는 문제이다.

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

그냥 바이너리 서치 문제이다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            
            if(mid == 0 || mid == nums.length - 1) {
                return nums[mid];
            } else if(nums[mid] == nums[mid - 1]) {
                if(mid % 2 == 1) l = mid + 1;
                else r = mid - 1;
            } else if(nums[mid] == nums[mid + 1]) {
                if(mid % 2 == 0) l = mid + 1;
                else r = mid - 1;
            } else {
                return nums[mid];
            }
        }
        
        return 0;
    }
}

제출 화면

이번에 외국인 친구들과 함께하는 스키여행을 가서 재밌게 즐겼다.

많은 친구들을 사귀었고 스키도 재밌었고 영어도 엄청 많이 해보고 카지노는 못가봤다 ㅠㅠ

담에도 하면 꼭 가야지!

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

2023년 02월 13일 월요일 - 아니 지난주 문제 너무 어렵자너..

오늘 올려볼 문제는 1523번 Count Odd Numbers in an Interval Range 이라는 문제이다.

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

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

근데 오늘은 그냥 알고리즘이라고 할 수도 없이 쉽자너..

입력

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

풀이 및 코드

주어진 int 2개 사이에 홀수가 몇개있는지 구하는 문제이다.

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

설명도 사치다..

이제 코드를 봐보자!

풀이코드

class Solution {
    public int countOdds(int low, int high) {
        return ((low % 2 == 1 || high % 2 == 1) ? 1 : 0) + (high - low ) / 2;
    }
}

제출 화면

아니 요즘 leetcode 난이도 조절 실화임?

중간이 없네..

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

2023년 02월 09일 목요일 - 오늘 금욜 아니었나..?

오늘 올려볼 문제는 2306번 Naming a Company 이라는 문제이다.

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

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

하드치고는 1트 클

입력

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

풀이 및 코드

1. 두 개의 단어를 고른다.
2. 두 개의 단어의 맨 앞글자를 서로 바꾼다.
3. 바꾼 단어가 ideas 배열에 둘 다 존재하지 않는다면 valid한 이름이다. (순서 상관있음)
4. 이외에는 invalid하다

이 규칙을 따르는 valid한 이름의 개수를 구하는 문제이다.

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

맨 앞글자만 서로 바꾸는 것이므로 HashSet 배열을 만들고 맨 앞글자를 index로 해서 뒤에 String 부분을 set에 저장했다.

이 후 모든 쌍에 대해서 교집합만큼 뺀 이후 곱해주고 2를 곱해주면 내가 원하는 값을 찾아낼 수 있었고 이런식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public long distinctNames(String[] ideas) {
        var arr = new HashSet[26];
        
        for(int i = 0; i < arr.length; i++) arr[i] = new HashSet<String>();
        
        for(var idea : ideas) arr[idea.charAt(0) - 'a'].add(idea.substring(1));
        
        long result = 0;
        
        for(int i = 0; i < arr.length - 1; i++) {
            for(int j = i + 1; j < arr.length; j++) {
                var set = new HashSet<String>();
                set.addAll(arr[i]);
                
                set.retainAll(arr[j]);
                int retainCnt = set.size();
                
                result += 2 * (arr[i].size() - retainCnt) * (arr[j].size() - retainCnt);
            }
        }
        
        return result;
    }
}

제출 화면

hard 문제인 것 치고는 너무 쉽게 풀어서 놀랐다.

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

2023년 02월 08일 수요일 - T1!

오늘 올려볼 문제는 45번 Jump Game II 이라는 문제이다.

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

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

아 생각보다 잘 못 풀어서 아쉽

입력

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

풀이 및 코드

각 원소에 있는 수의 길이를 최대로 점프할 수 있다고 할 때 배열의 끝까지 가장 적은 점프로 갈 수 있는 점프수를 구하는 문제이다.

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

dp를 사용하고 count를 저장하는데 최대로 점프뛸 수 있는곳에 이미 저장한 값이 있으면 넘어가고 없다면 해당 길이까지 모두 dp를 채워가는 식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        var arr = new int[n];
        
        if(n == 1) return 0;
        
        for(int i = 0; i < n; i++) {
            if(i + nums[i] >= n - 1) return arr[i] + 1;
            
            for(int j = i + 1; j <= i + nums[i]; j++) {
                if(arr[j] > arr[i] || arr[j] == 0) arr[j] = arr[i] + 1;
            }
        }
        
        return 0;
    }
}

제출 화면

discuss를 보니 훨씬 간단하면서 멋있고 섹시한 코드가 있었다.

이런 코드들을 잘 기억해두고 나중에 응요해봐야겠다.

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

2023년 02월 07일 화요일 - 야근시러

오늘 올려볼 문제는 904번 Fruit Into Baskets 이라는 문제이다.

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

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

문제 좀더 깔쌈하게 풀 수 있었는데 ㄲㅂ

입력

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

풀이 및 코드

과일을 따기 시작하면 계속 따야한다.

한 바구니에는 한 종류의 과일만 넣어야하며 바구니는 2개가 있다.

가장 많은 과일을 담을 수 있는 경우의 수를 구하는 문제이다.

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

오늘도 윈도우 슬라이딩....

이제 코드를 봐보자!

풀이코드

class Solution {
    public int totalFruit(int[] fruits) {
        int result = 0, diff = 0, index = 0, length = 0;
        var map = new HashMap<Integer, Integer>();
        
        for(var f : fruits) {
            map.put(f, map.getOrDefault(f, 0) + 1);
            if(map.get(f) == 1) diff++;
            length++;
            
            while(diff > 2) {
                map.put(fruits[index], map.get(fruits[index]) - 1);
                if(map.get(fruits[index++]) == 0) diff--;
                length--;
            }
            
            result = Math.max(result, length);
        }
        
        return result;
    }
}

제출 화면

사실 diff 변수를 안쓰고 hashmap의 size를 사용하는게 더 좋아보이긴 했다.

나중에는 좀 더 신경쓰면서 푸는걸로!

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