뒤죽박죽 코딩 이야기

2023년 04월 04일 화요일 - 왜 아직 화욜?

오늘 올려볼 문제는 2405번 Optimal Partition of String 이라는 문제이다.

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

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

아니 substring끼리도 unique해야하는 줄..

입력

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

풀이 및 코드

주어진 string을 substring으로 나누는데 각 substring들은 포함하는 원소가 unique해야한다.

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

window sliding으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int partitionString(String s) {
        var arr = new boolean[26];
        int left = 0, result = 1;
        
        for(int i = 0; i < s.length(); i++) {
            if(arr[s.charAt(i) - 'a']) {
                while(left < i) arr[s.charAt(left++) - 'a'] = false;
                result++;
            }
            arr[s.charAt(i) - 'a'] = true;
        }
        
        return result;
    }
}

제출 화면

요즘 문제를 잘못봐서 어렵게 푸는 경우가 늘고 있는 것 같다....

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

2023년 04월 03일 월요일 - 왜 아직 월욜?

오늘 올려볼 문제는 881번 Boats to Save People 이라는 문제이다.

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

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

아니 중요한거는 bold 좀 해놔!!!!!

입력

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

풀이 및 코드

limit 만큼 무게를 버틸 수 있고 최대 사람을 2명까지 태울 있는 배들이 있다.

이 때 모든 사람을 태울 수 있는 가장 적은 배의 개수를 구하는 문제이다.

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

정렬하고 투포인터를 사용했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int result = 0, left = 0;
        
        for(int right = people.length - 1; right >= left; right--) {
            if(people[left] <= limit - people[right]) left++;
            
            result++;
        }
        
        return result;
    }
}

제출 화면

아니 최대 2명까지 태울 수 있는 거 못봐서 개오래걸림;;;;

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

2023년 04월 02일 일요일 - 생일 선물 고마워욤~~

오늘 올려볼 문제는 2300번 Successful Pairs of Spells and Potions 이라는 문제이다.

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

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

아니 오버플로 형!!! 왜 이런거에 long을 쓰냐고오오오!!!

입력

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

풀이 및 코드

문제 설명이 조금 애매하다.. 문제 참고 바란다.

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

potions 배열을 정렬하고 바이너리 서치를 사용했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        
        for(int i = 0; i < spells.length; i++) {
            int left = 0, right = potions.length - 1;
            while(left <= right) {
                int mid = left + (right - left) / 2;
                
                if((long)potions[mid] * (long)spells[i] < success) left = mid + 1;
                else right = mid - 1;
            }
            
            spells[i] = potions.length - right - 1;
        }
        
        return spells;
    }
}

제출 화면

오늘 처음으로 석촌호수에서 벚꽃구경도 해보고 생일 선물도 받아따~

감사합니당 잘 입을게욤~~

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

2023년 04월 01일 토요일 - 대황티원!!!!

오늘 올려볼 문제는 704번 Binary Search 이라는 문제이다.

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

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

크으 역시 티원이야 너무 잘해

입력

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

풀이 및 코드

바이너리 서치를 구현하는 문제다.

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

그냥 바이너리 서치다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while(left <= right) {
            int mid = left + (right - left) / 2;
            
            if(nums[mid] == target) 
                return mid;
            else if(nums[mid] > target) 
                right = mid - 1;
            else
                left = mid + 1; 
        }
        
        return -1;
    }
}

제출 화면

티원 결승전 직행 너무 자랑스럽다.

LCK V11 가보자고!!!!

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

2023년 03월 29일 수요일 - 감기에 걸려따 ㅠ

오늘 올려볼 문제는 1402번 Reducing Dishes 이라는 문제이다.

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

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

any order를 못봐서 한참 고민했다..

입력

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

풀이 및 코드

오늘은 문제 설명이 조금 어렵다.. 사진 참고 바란다..

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

정렬 후 누적합 그리디로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        int n = satisfaction.length, sum = 0;
        var arr = new int[n + 1];
        
        Arrays.sort(satisfaction);
        
        for(int i = 1; i <= n; i++) {
            arr[i] = arr[i - 1] + satisfaction[i - 1];
            sum += satisfaction[i - 1] * i;
        }
        
        int result = Math.max(0, sum);
        
        for(int i = 0; i <= n; i++) {
            sum -= arr[n] - arr[i];
            result = Math.max(sum, result);
        }
        
        return result;
    }
}

제출 화면

오랜만에 목감기라서 조금 힘들다..ㅠㅠ

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

2023년 03월 28일 화요일 - 흠 아직도 화욜?

오늘 올려볼 문제는 983번 Minimum Cost For Tickets 이라는 문제이다.

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

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

아니 문제 개어려워!!

입력

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

풀이 및 코드

여행을 하려는 날짜와 1일, 7일, 30일 짜리 pass 권에 대한 가격이 주어진다.

이 때 모든 날을 여행할 수 있는 가장 적은 돈을 구하는 문제이다.

오늘은 정말 많이 헤매고 정답을 찾았다.

dp를 사용했고 set을 사용했다. (set은 사용안할 수도 있긴하다..)

1. dp 길이를 days에서 가장 큰 날짜 + 1로 정해주고 큰값으로 채워넣는다
2. 이 후 dp 배열을 돌면서 이전 1, 7, 30일 날짜 전에 쓴 돈 중에 어떤것이 제일 작은지 판단하여 dp 배열을 업데이트 한다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        var set = new HashSet<Integer>();
        for(var day: days) set.add(day);
        
        var ranges = new int[] {1, 7, 30};
        
        int n = days.length;
        var dp = new int[days[n - 1] + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        int pre = 0;
        
        for(int day = 0; day < dp.length; day++) {
            if(!set.contains(day)) {
                dp[day] = dp[pre];
                continue;
            }
            
            for(int j = 0; j < 3; j++) {
                int beforeDay = Math.max(day - ranges[j], 0), cost = costs[j];
                
                pre = day;
                
                dp[day] = Math.min(dp[beforeDay] + cost, dp[day]);
            }
        }
        
        return dp[days[n - 1]];
    }
}

제출 화면

days에 날짜가 떨어져있는 바람에 너무 헤맸다..

또한 O(n)으로도 풀 수 있는 문제라서.. 아직 dp는 많이 부족한 걸 느낀 하루였다.

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

2023년 03월 26일 일요일 - mt 힘들군요 ㅎㅎ

오늘 올려볼 문제는 2360번 Longest Cycle in a Graph 이라는 문제이다.

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

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

작년하고 거의 비슷한 mt 느낌 ㅎㅎ

입력

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

풀이 및 코드

int 배열로 각 인덱스에 해당하는 노드가 어떤 노드를 바라보고 있는지 주어진다. 즉 direct graph가 주어진다.

이 direct graph에 사이클이 있는지 확인하고 사이클이 있다면 가장 큰 사이클의 길이를 구하는 문제이다.

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

dfs로 순회하면서 사이클이 있는지 판단한다.

사이클이 존재한다면 해당 사이클의 길이를 구한다.

또한 어차피 순회를 한 곳에 사이클이 있건 없건 굳이 한 번 더 확인할 필요는 없으므로 boolean 배열을 이용해서 한 번만 순회하게했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    boolean[] visit;
    
    public int longestCycle(int[] edges) {
        visit = new boolean[edges.length];
        int result = -1;
        
        for(var edge : edges) {
            var node = findCycle(edges, new HashSet<>(), edge);
            
            if(node < 0) continue;
            
            int temp = edges[node], length = 1;
            
            for(; node != temp; length++) temp = edges[temp];
            
            result = Math.max(result, length);
        }
        
        return result;
    }
    
    public int findCycle(int[] edges, HashSet<Integer> set, int root) {
        if(root < 0) return -1;
        if(!set.add(root)) return root;
        if(visit[root]) return -1;
        
        visit[root] = true;
        
        return findCycle(edges, set, edges[root]);
    }
}

제출 화면

하드 문제인 것 치고는 쉽게 풀었다.

mt를 이렇게 많은 동기들하고 간 건 처음인데 정말 재밌었다.

나중에 작년처럼 20끼리만 한 번 다시 갔으면 좋겠다.

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

2023년 03월 23일 목요일 - 한화생명... 굉장하다..!

오늘 올려볼 문제는 1319번 Number of Operations to Make Network Connected 이라는 문제이다.

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

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

아니 이걸 한화가 이기네 ㄷㄷ

입력

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

풀이 및 코드

n개의 컴퓨터와 컴퓨터끼리 연결되어있는 연결선들이 입력으로 들어온다.

모든 컴퓨터가 연결되도록 하게끔 연결선을 바꿔끼는 최소 횟수를 구하는 문제이다.

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

Union Find를 사용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int makeConnected(int n, int[][] connections) {
        if(connections.length < n - 1) return -1;
        
        var sets = new boolean[n];
        var arr = setUnion(n, connections);
        int result = -1;
        
        for(var num : arr) {
            if(sets[num]) continue;
            
            result++;
            sets[num] = true;
        }
        
        return result;
    }
    
    private int[] setUnion(int n, int[][] connections) {
        int[] arr = new int[n];
        
        for(int i = 0; i < arr.length; i++) arr[i] = i;
        
        for(var connection : connections) {
            int a = findUnion(arr, connection[0]);
            int b = findUnion(arr, connection[1]);
            
            if(a < b) arr[b] = a;
            else arr[a] = b;
        }
        
        for(int i = 0; i < arr.length; i++) findUnion(arr, i);
        
        return arr;
    }
    
    private int findUnion(int[] arr, int n) {
        if(arr[n] == n) return n;
        
        return arr[n] = findUnion(arr, arr[n]);
    }
}

제출 화면

내일은 연차 룰루랄라~~

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