뒤죽박죽 코딩 이야기

2022년 03월 08일 화요일 - 낼 쉰다 헤헿헿

오늘 올려볼 문제는 141번 Linked List Cycle 이라는 문제이다.

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

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

이 문제랑 비슷한 문제를 스터디에서 바로 어제 다뤘는데 더 쉬운게 나와서 이거 원... ㅋㅋㅋㅋ

입력

사진에서도 볼 수 있듯이 Linked List 하나가 입력으로 들어온다.

풀이 및 코드

주어진 Linked List에 cycle이 존재하는지 판단하여 리턴하는 문제다.

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

노드 2개를 만들어 하나는 1개씩 움직이고 다른 하나는 2개씩 움직여서 만나면 true, 만나지 않고 null이 되면 false를 리턴한다.

이제 코드를 봐보자!

풀이코드

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null)
            return false;

        ListNode slow = head.next, fast = head.next.next;

        while(slow != null && fast != null)
        {
            if(slow == fast)
                return true;
            try
            {
                slow = slow.next;
                fast = fast.next.next;
            }
            catch(Exception e)
            {
                break;
            }
        }

        return false;
    }
}

제출 화면

오늘 문제는 바로 어제 스터디에서 다뤘던 문제라서 너무 쉽게 풀었다.

내일은 좀 적당히 어렵고 재밌는 문제가 나왔으면 좋겠다.

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

2022년 03월 07일 월요일 - 월요일이 시작됐다....................

오늘 올려볼 문제는 21번 Merge Two Sorted Lists 이라는 문제이다.

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

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

쓸게 좀 있어서 3분컷!

입력

사진에서도 볼 수 있듯이 정렬된 LinkedList 2개가 입력으로 들어온다.

풀이 및 코드

LinkedList 2개를 merge 하여 리턴하는 문제다.

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

그냥 직관대로 풀면된다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode result = new ListNode();
        ListNode now = result;
        while(list1 != null && list2 != null)
        {
            if(list1.val > list2.val)
            {
                now.next = list2;
                list2 = list2.next;
            }
            else
            {
                now.next = list1;
                list1 = list1.next;
            }
            now = now.next;
        }

        while(list1 != null)
        {
            now.next = list1;
            list1 = list1.next;
            now = now.next;
        }

        while(list2 != null)
        {
            now.next = list2;
            list2 = list2.next;
            now = now.next;
        }

        return result.next;
    }
}

제출 화면

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

내일은 재밌는 적당히 어려운 문제가 나왔으면 좋겠다.

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

2022년 03월 06일 일요일 - 오늘은 노가다로 품... ㅎㅎ

오늘 올려볼 문제는 1359번 Count All Valid Pickup and Delivery Options 이라는 문제이다.

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

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

와 근데 다른 풀이 보니깐 개쩔더라

입력

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

풀이 및 코드

int 값 개수만큼 pickup을 하고 delivery를 할 수 있는 경우의 수를 찾아서 리턴하는 문제다.

이 때 delivery는 무조건 pickup을 한 뒤에 가능하다.

오늘은 걍 노가다로 풀고 정답을 봤는데 진짜 생각도 못한 방법이 있었다.

일단 n이 1일 때를 그림으로 보자면 __ P1 __ D1 __ 과 같이 표현가능하다.

이 때 P2, D2를 넣을 수 있는 가지수를 생각해보면 3 + 2 + 1 이다.

P1 앞에 P2를 넣는 경우 <- D2는 P2 뒤에만 있으면 되므로 3가지 공백에 모두 들어갈 수 있음 (P2 바로 뒤까지 포함)
D1 앞에 P2를 넣는 경우 <- D2는 P2 뒤에만 있으면 되므로 2가지 공백에 들어갈 수 있음
D1 뒤에 P2를 넣는 경우 <- D2는 P2 뒤에만 있으면 되므로 1가지 공백에 들어갈 수 있음

즉 지금 구하려는 수의 1을 뺀 수로 계산해둔 값에 공백에 넣을 수 있는 가지수를 곱하기만 하면 이번에 나올 값을 쉽게 구할 수 있는 것이다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int countOrders(int n) {
        long result = 1;
        int diff = 9, mul = 6;
        n--;
        while(n > 0)
        {
            result *= mul;
            mul += diff;
            diff += 4;
            result %= 1000000007;
            n--;
        }

        return (int)result;
    }
}

위에서 설명한 알고리즘 기법을 사용한 풀이다.

풀이코드

class Solution {
    public int countOrders(int n) {
        int mod = 1000000007;
        long result = 1;
        for(int i = 2; i <= n; i++)
        {
            int space = (i - 1) * 2 + 1;
            result = result * (space * (space + 1) / 2);
            result %= mod;
        }

        return (int)result;
    }
}

제출 화면

오늘 다른 사람들의 풀이를 보고 좀 충격을 받았다.

그렇게 어렵지 않은 접근이었는데 이걸 생각을 못했다는 것에 좀 화가났던 것도 있었던 것 같다.

그래도 문제는 풀었으니... 다행이라고 생각한다. ㅋㅋㅋㅋㅋㅋ

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

2022년 03월 05일 토요일 - 어제는 미디엄인데 개어렵고 오늘은 재밌고... 참....

오늘 올려볼 문제는 740번 Delete and Earn 이라는 문제이다.

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

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

dp 문제라서 조금 어렵긴했지만 재밌었다!

입력

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

풀이 및 코드

배열에서 하나의 원소를 삭제하고 그 만큼 돈을 번다. 이 때 원소 + 1, 원소 - 1에 해당하는 모든 원소들을 지운다.

이러한 과정을 거쳤을 때 가장 많이 벌 수 있는 돈을 구하고 리턴하는 문제다.

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

뭔가 다른 방법으로 접근했을 때 예외가 많이 생기는 것을 보아하니 dp 문제인 것 같아서 dp로 접근했다.

dp에는 현재까지 가장 큰 값을 저장한다.

dp[i - 2] + arr[i] 와 dp[i] 를 비교하는데 이는 i 보다 2작은 원소를 선택하는 것이 좋은지 아니면 i 보다 1 작은 원소를 선택하는 것이 좋은지 판단하는 부분이다.

(사실 dp는 작은 입력값으로 직접 그려보면서 값이 어떻게 변하는지 확인해야 이해가 그나마 쉽다.)

이제 코드를 봐보자!

풀이코드

class Solution {
    public int deleteAndEarn(int[] nums) {
        int[] arr = new int[10005];
        int[] dp = new int[10005];

        for(int num : nums)
        {
            arr[num] += num;
        }

        dp[1] = dp[2] = arr[1];

        for(int i = 2; i <= 10000; i++)
        {
            if(dp[i - 2] + arr[i] > dp[i])
            {
                dp[i] = dp[i - 2] + arr[i];
            }
            dp[i + 1] = dp[i];
        }

        return dp[10000];
    }
}

제출 화면

오래만에 내 맘에드는 재밌는 문제가 나온 것 같다.

내일도 이런 문제가 나왔으면 좋겠다!

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

2022년 03월 03일 목요일 - 오늘은 블랙잭으로 칩 벌어서 적립하고 옴!

오늘 올려볼 문제는 413번 Arithmetic Slices 이라는 문제이다.

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

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

아니 차이라고만 하면 당연히 절대값으로 생각하지 왜 이거 때문에 틀리게하냐구!!

입력

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

풀이 및 코드

원소가 3개 이상이면서 붙어있는 원소 2개의 차이가 모두 같은 subarray의 개수를 찾아 리턴하는 문제다.

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

그냥 쭉 가면서 차이를 비교하고 3개 이상이면 나올 수 있는 subarray 개수를 더해주는 식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if(nums.length < 3)
            return 0;

        int result = 0;
        int first = 0, last = -1;
        int diff = nums[0] - nums[1];

        for(int i = 1; i < nums.length - 1; i++)
        {
            if(nums[i] - nums[i + 1] != diff)
            {
                if(last - first + 1 >= 3)
                {
                    result += calc(last - first + 1);
                }

                first = i;
                last = i + 1;
                diff = nums[i] - nums[i + 1];
            }
            else
            {
                last = i + 1;
            }
        }

        if(last - first + 1 >= 3)
        {
            result += calc(last - first + 1);
        }

        return result;
    }

    public int calc(int num)
    {
        int result = 0;
        for(int i = 3; i <= num; i++)
        {
            result += num + 1 - i;
        }
        return result;
    }
}

제출 화면

오늘 문제가 좀 중의적이라서 좀 시행착오를 겪었다.

풀고나서 좀 화가났지만 그래도 뭐 내일 문제는 좋을 것이라 생각하면서 넘어갔다.

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

2022년 03월 02일 수요일 - 난 오늘도 금요일인 남자

오늘 올려볼 문제는 392번 Is Subsequence 이라는 문제이다.

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

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

왜 수요일까지 문제가 이렇게 쉽지...?

입력

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

풀이 및 코드

s가 t의 subsequence인지 판단하여 리턴하는 문제이다.

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

for문으로 t의 모든 원소들을 하나씩 보는데 이 때 s와 같다면 s를 보는 index도 하나씩 올려간다.

마지막에 index가 s의 길이와 같은지를 리턴하는 방식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean isSubsequence(String s, String t) {
        int index = 0;
        for(int i = 0; i < t.length(); i++)
        {
            try
            {
                if(s.charAt(index) == t.charAt(i))
                {
                    index++;
                }
            }
            catch(Exception e)
            {
                break;
            }
        }

        return index == s.length();
    }
}

제출 화면

아직도 문제가 쉬워서 조금 의아하긴 하지만 내일 문제는 조금 어려울 것으로 예상한다.

내일은 좀 재밌는 문제가 나오길 바란다.

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

2022년 03월 01일 화요일 - 아우 쉬는날 너무 조아

오늘 올려볼 문제는 338번 Counting Bits 이라는 문제이다.

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

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

사실 O(n log n)에 풀었다가 Discuss보고 O(n)으로 풀었다.. ㅋㅋㅋ

입력

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

풀이 및 코드

주어진 n까지의 수를 2진수로 봤을 때 1이 몇개씩 있는지 배열에 저장하고 리턴하는 문제다.

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

각 index가 0이 될 때가지 2로 나누고 나머지가 1이라면 1을 더하는 식으로 구현했다.

하지만 O(n)으로 문제를 풀려고 고민하다가 하나 놓친 부분을 discuss에서 얻었다.

나는 쉬프트 연산을 하면서 2로 나누어지는 것 때문에 맨처음 비트를 계산하려 했지만 사실 맨 마지막 비트를 계산하여야 했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for(int i = 0; i <= n; i++)
            result[i] = result[i >> 1] + (i & 1);
        return result;
    }
}

제출 화면

사실 난 O(n log n)으로 풀었지만... 지금 올린 O(n) 풀이도 내 의지가 들어가긴 했으니... 올리겠다 ㅋㅋㅋㅋㅋ

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

2022년 02월 28일 월요일 - 이번주는 금요일만 존재한다!!

오늘 올려볼 문제는 228번 Summary Ranges 이라는 문제이다.

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

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

자동화되어서 올라가는 포스트... 살짝 맘에 안들지만... 뭐 편하니깐

입력

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

풀이 및 코드

정렬된 배열 중 이어져있는 배열들의 범위들을 리턴하는 문제다. (말로 설명하기 힘들다... 문제를 참고해주시길..)

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

그냥 직관적으로 풀면 풀린다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<String>();
        int first = -1, last = -1;
        boolean flag = true;
        if(nums.length == 0)
        {
            return result;
        }

        for(int i = 0; i < nums.length; i++)
        {
            if(flag)
            {
                first = nums[i];
                last = nums[i];
                flag = false;
                continue;
            }

            if(nums[i] - 1 == nums[i - 1])
            {
                last = nums[i];
            }
            else
            {
                if(first == last)
                {
                    result.add(Integer.toString(first));
                }
                else
                {
                    result.add(first + "->" + last);
                }

                flag = true;
                i--;
            }
        }

        if(first == last)
        {
            result.add(Integer.toString(first));
        }
        else
        {
            result.add(first + "->" + last);
        }

        return result;
    }
}

제출 화면

오늘은 문제가 쉬워서 금방 풀었다.

원래 주의 시작은 문제가 쉬웠고 토요일이 항상 어려웠는데... 이번주도 그럴거 같아서 벌써 긴장이된다..

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