뒤죽박죽 코딩 이야기

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

제출 화면

내일은 연차 룰루랄라~~

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

2023년 03월 22일 수요일 - PO 꿀잼

오늘 올려볼 문제는 2492번 Minimum Score of a Path Between Two Cities 이라는 문제이다.

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

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

왜 아직도 수욜이니

입력

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

풀이 및 코드

1번 노드부터 n번 노드까지 있는 그래프가 있다.

roads를 통해서 이어져있는 길과 길의 길이를 입력으로 준다.

이 때 1번 노드부터 n번 노드로 가는 길 중에 가장 짧은 노드 사이의 거리의 길이를 구하는 문제이다. (설명하기가 힘들다..)

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

Union Find로 1번 노드와 연결된 노드들을 구하고 최소값을 구했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int minScore(int n, int[][] roads) {
        int[] arr = new int[n + 1];
        
        for(int i = 0; i < n + 1; i++) arr[i] = i;
        
        for(var road : roads) {
            int a = findUnion(arr, road[0]);
            int b = findUnion(arr, road[1]);
            
            if(a < b) arr[b] = a;
            else arr[a] = b;
        }
        
        int result = Integer.MAX_VALUE;
        
        for(var road : roads) {
            if(findUnion(arr, road[0]) == 1) result = Math.min(result, road[2]);
        }
        
        return result;
    }
    
    private int findUnion(int[] arr, int n) {
        if(arr[n] == n) return n;
        
        return findUnion(arr, arr[n]);
    }
}

제출 화면

어후 요즘 너무 졸려

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

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

오늘 올려볼 문제는 2348번 Number of Zero-Filled Subarrays 이라는 문제이다.

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

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

이게 왜 이지가 아님?

입력

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

풀이 및 코드

0으로만 이루어진 subarray의 총 개수를 구하는 문제이다.

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

0으로만 이루어진 subarray의 길이를 구하는 과정에서 모든 길이를 더해주면 답이 나온다. (0으로만 이루어진 배열에서 만들 수 있는 subarray의 개수가 1부터 n까지의 합과 같기 때문)

이제 코드를 봐보자!

풀이코드

class Solution {
    public long zeroFilledSubarray(int[] nums) {
        int length = 1;
        long result = 0;
        
        for(var num: nums) {
            if(num == 0) result += length++;
            else length = 1;
        }
        
        return result;
    }
}

제출 화면

알고리즘 스터디를 진행했더니 블로그 쓰는걸 까먹을 뻔 했다 ㅎㅎ

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