뒤죽박죽 코딩 이야기

2022년 04월 06일 수요일 - 회식 다음날은 너무 힘들다...

오늘 올려볼 문제는 923번 3Sum With Multiplicity 이라는 문제이다.

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

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

오늘 뇌가 굳은거 가타따..

입력

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

풀이 및 코드

인덱스 i, j, k 가 i < j < k 를 만족하면서 모두 더한 값이 target이 되는 경우의 수가 몇인지 구하는 문제다.

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

각 숫자의 개수를 저장한다.

i, j는 for문을 돌면서 찾고 k는 target에서 i, j를 뺀 값으로 찾는다.

i == j == k 일 때, i == j != k 일 때, j < k 일 때를 나누어서 계산하는 방법으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int threeSumMulti(int[] nums, int target) {
        long[] count = new long[105];
        int mod = 1000000007;
        long result = 0;

        for(int num : nums) count[num]++;

        for(int i = 0; i <= 100; i++)
        {
            for(int j = i; j <= 100; j++)
            {
                int k = target - i - j;
                if(k > 100 || k < 0) continue;

                if(i == j && j == k)
                {
                    result += count[i] * (count[i] - 1) * (count[i] - 2) / 6;
                }
                else if(i == j && j != k)
                {
                    result += count[i] * (count[i] - 1) / 2 * count[k];
                }
                else if(j < k)
                {
                    result += count[i] * count[j] * count[k];
                }
            }
        }

        return (int)(result % mod);
    }
}

제출 화면

어제 회식의 여파로 머리가 굳은 거 같아서 꽤 힘들게 문제를 풀었다.

내일은 좀 잘 풀었으면 좋겠다.

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

2022년 04월 04일 월요일 - 왜... 월요일...?

오늘 올려볼 문제는 1721번 Swapping Nodes in a Linked List 이라는 문제이다.

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

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

아니 Value만 바꿔도 되는거 왜 안알려줬어!!!!

입력

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

풀이 및 코드

앞에서 k번째 node와 뒤에서 k번째 node를 바꾸어서 리턴하는 문제다.

오늘은 시행착오를 좀 겪었다.

정석적으로 바꾸려는 node들의 앞뒤를 저장해서 이어주고 떼주고... 하다가 너무 힘들어서 HashMap을 사용해서 indexing을 하고 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        HashMap<Integer, ListNode> map = new HashMap<>();
        int length = 0;
        ListNode start = head, end = head;

        for(;start != null; start = start.next)
        {
            length++;
            map.put(length, start);
        }

        if(length == 1) return head;

        if(k > length / 2) k = length - k + 1;

        if(length == 2)
        {
            map.get(1).next = null;
            map.get(2).next = map.get(1);

            return map.get(2);
        }
        else if(k == 1)
        {
            map.get(1).next = null;
            map.get(length).next = map.get(2);
            map.get(length - 1).next = map.get(1);

            return map.get(length);
        }
        else if(2 * k == length)
        {
            map.get(k - 1).next = map.get(k + 1);
            map.get(k + 1).next = map.get(k);
            map.get(k).next = map.get(k + 2);

            return head;
        }
        else
        {
            map.get(k - 1).next = map.get(length - k + 1);
            map.get(length - k + 1).next = map.get(k + 1);
            map.get(length - k).next = map.get(k);
            map.get(k).next = map.get(length - k + 2);

            return head;
        }
    }
}

제출 화면

사실 value만 바꿔도 되는줄 알았으면 훨씬 쉽게 문제를 풀었을 것이다.

내일은 좀 꼼수를 부리더라도 편하게 풀어야겠다.

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

2022년 04월 03일 일요일 - 오늘을 데이뚜

오늘 올려볼 문제는 31번 Next Permutation 이라는 문제이다.

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

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

거의 다 풀고 틀려서 힌트 봤지만 올릴거임!

입력

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

풀이 및 코드

해당 배열로 만들 수 있는 조합들중 다음 조합에 해당하는 배열을 만드는 문제이다.

이 때 입력으로 들어온 배열을 수정하는 방식으로 구현해야한다.

오늘은 틀렸지만 방향성은 맞았다.

일단 앞의 숫자가 뒤에 나오는 숫자보다 작을 때를 찾는다.

이 숫자 뒤에 나오는 숫자중 가장 작은 수랑 위치를 바꾸고 이 숫자 뒤로 정렬을 하는 식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public void nextPermutation(int[] nums) {
        int lastIndex = -1;
        for(int i = 0; i < nums.length - 1; i++)
        {
            if(nums[i] < nums[i + 1]) lastIndex = i;
        }

        if(lastIndex == -1)
        {
            Arrays.sort(nums);
        }
        else
        {
            int minIndex = lastIndex + 1;
            for(int i = lastIndex + 1; i < nums.length; i++)
            {
                if(nums[lastIndex] < nums[i] && nums[i] < nums[minIndex]) minIndex = i;
            }

            int temp = nums[minIndex];
            nums[minIndex] = nums[lastIndex];
            nums[lastIndex] = temp;

            Arrays.sort(nums, lastIndex + 1, nums.length);
        }
    }
}

제출 화면

오늘은 마음이 급해서 힌트를 빨리봤는데 아마 고민을 좀만 더 했으면 힌트 없이 문제를 풀었을 것이다.

내일은 성인군자와 같은 마음으로 문제를 풀어야겠다.

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

2022년 04월 02일 토요일 - 으어어어 뇌가 굳었나...

오늘 올려볼 문제는 680번 Valid Palindrome II 이라는 문제이다.

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

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

easy 문제에 시간 30분 쓴거는 또 처음이네...

입력

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

풀이 및 코드

최대 한글자를 지울 수 있다고 했을 때 주어진 String이 palindrome인지 판단하여 리턴하는 문제다.

오늘은 시행착오를 좀 겪었다.

처음에는 재귀를 사용하려 했는데 생각보다 예외처리할게 많아져서 스택을 사용하려 했는데 스택도 예외처리할게 많았다.

그래서 결국 생각한 방법은 처음 양쪽 끝이 달라지는 부분을 찾고 양쪽 하나씩 뺀다음에 비교하는 방법으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean validPalindrome(String s) {
        int index = 0;
        boolean flag = false;
        for(index = 0; index <= (s.length() + 1) / 2; index++)
        {
            if(s.charAt(index) != s.charAt(s.length() - 1 - index))
            {
                flag = true;
                break;
            }
        }

        if(flag)
        {
            flag = false;

            for(int i = index; i < (s.length() + 1) / 2; i++)
            {
                if(s.charAt(i + 1) != s.charAt(s.length() - 1 - i))
                {
                    flag = true;
                    break;
                }
            }

            if(flag)
            {
                for(int i = index; i < (s.length() + 1) / 2; i++)
                {
                    //System.out.println(s.charAt(i) + " " + s.charAt(s.length() - 2 - i));
                    if(s.charAt(i) != s.charAt(s.length() - 2 - i)) return false;
                }
            }

        }

        return true;
    }
}

제출 화면

easy 문제를 이렇게나 오래동안 풀었다는 거에 좀 충격을 받았다..

내일은 잘 풀 수 있었으면 좋겠다...

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

2022년 04월 01일 금요일 - 오앙 4월이당

오늘 올려볼 문제는 344번 Reverse String 이라는 문제이다.

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

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

아니 거 문제가 너무 쉬운거 아니오!

입력

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

풀이 및 코드

주어진 char 배열을 뒤집는 문제이다.

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

그냥 양쪽 끝을 swap하면서 절반만큼 돌면 된다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public void reverseString(char[] s) {
        char temp;
        for(int i = 0; i < s.length / 2; i++)
        {
            temp = s[i];
            s[i] = s[s.length - 1 - i];
            s[s.length - 1 - i] = temp;
        }
    }
}

제출 화면

오늘 문제는 너무 쉬워서 재미없었다.

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

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

2022년 03월 29일 화요일 - 오늘은 왜 이렇게 시간이 안가나요~~

오늘 올려볼 문제는 287번 Find the Duplicate Number 이라는 문제이다.

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

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

1분 컷이지만 follow up은 못 풀었다는 사실

입력

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

풀이 및 코드

길이가 n + 1인 배열에 1 ~ n까지의 원소가 있는데 이 때 딱 한 원소만이 중복된다고 할 때 이 중복된 원소를 찾아서 리턴하는 문제이다.

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

중복된 원소가 나왔는지 판단하는 boolean 배열을 만들고 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findDuplicate(int[] nums) {
        boolean[] count = new boolean[nums.length];

        for(int num : nums)
        {
            if(count[num])
                return num;
            else
                count[num] = true;
        }

        return 0;
    }
}

아래 코드는 공간복잡도 O(1)인 풀이이다.

풀이코드

class Solution {
    public int findDuplicate(int[] nums) {
        int fast = 0, slow = 0;
        fast = nums[nums[fast]];
        slow = nums[slow];

        while(nums[fast] != nums[slow])
        {
            fast = nums[nums[fast]];
            slow = nums[slow];
        }

        fast = 0;
        while(nums[fast] != nums[slow])
        {
            fast = nums[fast];
            slow = nums[slow];
        }

        return nums[fast];
    }
}

제출 화면

사실 내가 즐겨봤던 Joma Tech 채널에 소개됐던 문제랑 완전 똑같은 문제였는데..

거기서 소개된 해결방안을 생각못한게 많이 아쉽다...

내일은 간지나게 문제를 풀 수 있으면 좋겠다.

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

2022년 03월 28일 월요일 - 이거 이렇게 푼거 올려도 되나..?

오늘 올려볼 문제는 81번 Search in Rotated Sorted Array II 이라는 문제이다.

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

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

올릴까 말까 고민 마이 해따..

입력

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

풀이 및 코드

정렬된 배열을 어떠한 수만큼 돌린 배열이 주어질 때 target이 배열안에 있는지 판단하는 문제이다.

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

사실상 걍 for문 돌리면서 문제를 풀어도 풀리지 않을까 했는데 진짜 풀렸다...

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean search(int[] nums, int target) {
        for(int num : nums) if(num == target) return true; return false;
    }
}

정석적인 풀이는 아래와 같다.

풀이코드

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;

        while(left <= right)
        {
            mid = (left + right) / 2;

            if(nums[mid] == target) return true;

            if(nums[mid] < nums[left] || nums[mid] < nums[right])
            {
                if(nums[mid] < target && target <= nums[right])
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
            else if(nums[mid] > nums[left] || nums[mid] > nums[right])
            {
                if(nums[left] <= target && target < nums[mid])
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            else
            {
                right--;
            }
        }

        return false;
    }
}

제출 화면

사실 제대로 된 풀이로 문제를 푼게 아니라서 올리지말까하다가 풀긴 풀었으니 올린다...

내일은 제대로 된 풀이로 문제를 풀 수 있기를 바란다.

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

2022년 03월 27일 일요일 - 오느른 데이뚜

오늘 올려볼 문제는 1337번 The K Weakest Rows in a Matrix 이라는 문제이다.

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

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

오늘 문제도 쉽구만

입력

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

풀이 및 코드

각 2차원 배열의 row 중 1의 개수가 적은 row 들부터, index가 더 작은 row 들부터 길이가 k인 배열에 index를 담아 리턴하는 문제다.

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

pair 클래스를 만들고 comparator를 구현해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        pair[] arr = new pair[mat.length];
        int[] result = new int[k];

        for(int i = 0; i < mat.length; i++)
        {
            int sum = 0;
            for(int num : mat[i]) sum += num;
            arr[i] = new pair(sum, i);
        }

        Arrays.sort(arr, (p1, p2) -> {return p1.val == p2.val ? p1.index - p2.index : p1.val - p2.val;});

        for(int i = 0; i < k; i++)
            result[i] = arr[i].index;

        return result;
    }
}

class pair
{
    int val, index;

    public pair(int val, int index)
    {
        this.val = val;
        this.index = index;
    }
}

제출 화면

어제 오늘 문제가 너무 쉬운것 같다.

내일 문제는 좀 어려우면서 재밌는 문제가 나왔으면 좋겠다.

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