뒤죽박죽 코딩 이야기

2022년 2월 09일 수요일 - 오늘 너무 졸렸다아아....

오늘 올려볼 문제는 532번 K-diff Pairs in an Array 이라는 문제이다.

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

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

오늘도 푸는데 오래걸리지 않았다!

입력

사진에서도 볼 수 있듯이 int 배열 1개와 int 1개가 주어진다.

풀이 및 코드

주어진 하나의 int 숫자만큼 차이나는 쌍이 배열에 몇개 있는지 구하는 문제이다.

이 때 쌍은 중복되지 않아야한다.

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

먼저 배열을 정렬한다.

일단 각 원소의 개수를 저장하는 해쉬맵을 만들고 저장한다.

k가 0이라면 각 원소의 개수가 2 이상일 때 결과값에 1을 더한다. (이 때 각 원소는 중복되지 않게 탐색해야한다.)

k가 0이 아니라면 각 원소의 k를 더한 값이 해쉬 맵에 있는지 판단하고 있다면 결과값에 1을 더한다. (이 때 각 원소는 중복되지 않게 탐색해야한다.)

이런식으로 시간복잡도 O(NlogN)에 풀 수 있는 방법을 생각해냈다. (해쉬맵에 foreach 구문을 달면 O(N)으로 가능하지만 자바로는 문법이 귀찮아서 그냥 정렬을 하느라 O(NlogN)에 풀었다.)

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findPairs(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        Arrays.sort(nums);
        // pre는 중복 원소를 피하기 위한 장치
        int result = 0, pre = -20000000;

        for(int i = 0; i < nums.length; i++)
        {
            if(!map.containsKey(nums[i]))
                map.put(nums[i], 0);

            map.put(nums[i], map.get(nums[i]) + 1);
        }

        if(k == 0)
        {
            for(int i = 0; i< nums.length; i++)
            {
                if(pre == nums[i])
                    continue;

                pre = nums[i];

                if(map.get(nums[i]) >= 2)
                    result++;
            }
        }
        else
        {   
            for(int i = 0; i < nums.length; i++)
            {
                if(pre == nums[i])
                    continue;

                pre = nums[i];

                if(map.containsKey(nums[i] + k))
                    result++;
            }
        }

        return result;
    }
}

제출 화면

오늘은 어렵지 않게 풀었던 문제였다.

하지만 해쉬맵에 foreach를 사용하는 생각은 아직도 바로바로 떠오르는 생각은 아니라서 좀 더 익숙해져야겠다.

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

2022년 2월 08일 화요일 - 오늘 첫 야근 해봄...

오늘 올려볼 문제는 258번 Add Digits 이라는 문제이다.

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

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

오늘은 1분컷!

입력

사진에서도 볼 수 있듯이 int 1개가 주어진다.

풀이 및 코드

주어진 하나의 int 숫자를 각 자리수를 모두 더한 값이 1자리 수가 될 때 까지 반복하여 나온 결과를 리턴하는 문제다.

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

일단 결과를 저장하는 변수에 입력받은 수를 저장한다.

입력받은 수가 0이 될 때까지 10의 나머지를 결과값에 더하고 10으로 더한다.

결과값이 10 미만이 될 때까지 위 과정을 반복한다.

이런식으로 시간복잡도 O(logN)에 풀 수 있는 방법을 생각해냈다.

이제 코드를 봐보자!

오늘은 숏코딩 한 코드도 가져왔으니 한 번 구경하시라! ㅋㅋㅋ

풀이코드

class Solution {
    public int addDigits(int num) {
        int result = num;

        while(result >= 10)
        {
            num = result;
            result = 0;

            while(num != 0)
            {
                result += num % 10;
                num /= 10;
            }
        }

        return result;
    }
}

숏코드

class Solution {
    public int addDigits(int num) {
        while(num >= 10){int i = num; num = 0;for(; i != 0; i /= 10) num += i % 10;} return num;
    }
}

제출 화면

오늘은 어렵지 않게 풀었던 문제였다.

요즘 문제가 계속 쉬워서 뭔가 아쉽다..

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

2022년 2월 07일 월요일 - 으어어 월요일...

오늘 올려볼 문제는 389번 Find the Difference 이라는 문제이다.

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

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

오늘은 3분컷!

입력

사진에서도 볼 수 있듯이 string 2개가 주어진다.

풀이 및 코드

주어진 하나의 string과 같은 원소들을 가지고 있지만 위치는 랜덤인 string에 하나의 char을 추가했을 때 추가된 char을 찾아서 리턴하는 문제다.

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

string을 구성하는 원소의 개수를 저장하는 int배열을 만든다.

첫번째 string을 구성하는 원소는 배열에 더하고, 두번째 string을 구성하는 원소는 배열에 뺐다.

모든 과정이 끝난 후 배열을 탐색했을 때 개수가 0이 아닌 index가 추가된 char다.

이런식으로 시간복잡도 O(N)에 풀 수 있는 방법을 생각해냈다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public char findTheDifference(String s, String t) {
        char[] arr = new char[30];

        for(int i = 0; i < s.length(); i++)
        {
            arr[s.charAt(i) - 'a']++;
            arr[t.charAt(i) - 'a']--;
        }
        arr[t.charAt(t.length() - 1) - 'a']--;

        for(int i = 0; i < arr.length; i++)
        {
            if(arr[i] != 0)
                return (char)('a' + i);
        }

        return 'a';

    }
}

제출 화면

오늘은 어렵지 않게 풀었던 문제였다.

문제에 대한 고민을 거의 안해서 오늘은 뭔가 문제를 안풀었다고 생각이 들 정도의 날이었다. ㅋㅋㅋㅋㅋㅋㅋ

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

2022년 2월 06일 토요일 - 오늘은 데이트~~

오늘 올려볼 문제는 80번 Remove Duplicates from Sorted Array II 이라는 문제이다.

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

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

오늘은 데이트 때문에 밖에서 폰으로 문제를 풀었다 ㅋㅋㅋㅋ

입력

사진에서도 볼 수 있듯이 정렬된 int 배열이 주어진다.

풀이 및 코드

정렬된 int 배열 중 중복되는 원소가 최대 2개까지 되게끔 배열을 수정하고 수정한 후 배열의 길이를 리턴하는 문제이다.

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

전 값을 저장하는 변수와 그 값의 개수를 저장하는 변수를 만든다.

또한 배열을 수정할 위치를 index를 저장하는 변수도 만든다.

값의 개수가 2개 초과일 때는 index 값을 올리지 않는 식으로 구현했다.

이런식으로 시간복잡도 O(N)에 풀 수 있는 방법을 생각해냈다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int removeDuplicates(int[] nums) {
        // pre는 전 값을 저장하는 변수, count는 pre의 개수 저장하는 변수, index는 새로 수정할 배열의 인덱스를 저장하는 변수
        int pre = -100000, count = 0, index = 0;

        for(int i = 0; i < nums.length; i++)
        {
            // 만약 새로운 값이 나온다면
            if(pre != nums[i])
            {
                pre = nums[i];
                count = 0;
                // 수정될 배열에 업데이트 한다.
                nums[index++] = nums[i];
            }
            // 만약 중복되는 값이 나온다면
            else
                // 중복되는 값의 개수가 2개가 이하라면
                if(count < 2)
                    // 수정될 배열에 업데이트 한다.
                    nums[index++] = nums[i];

            count++;
        }

        return index;
    }
}

제출 화면

오늘은 어렵지 않게 풀었던 문제였다.

다만 핸드폰으로 문제를 푼 건 처음이라서 생각보다는 어려웠다. ㅋㅋㅋㅋ

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

2022년 2월 05일 토요일 - 히히 쉬는 날이 젤 조아

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

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

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

Hard라는 글자를 보자마자 오늘은 블로그에 글 못올리나 했다..

입력

사진에서도 볼 수 있듯이 정렬된 링크드 리스트 배열이 주어진다.

풀이 및 코드

정렬된 링크드 리스트 들을 하나로 merge 하는 문제이다.

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

링크드 리스트에 들어있는 값의 범위가 -10,000 부터 10,000까지라서 크기가 20,005 int 배열을 하나 만들었다.

각 인덱스에 해당하는 숫자의 개수를 저장하는 배열로 사용한다.

모든 링크드 리스트에 들어있는 숫자를 인덱스로 사용하여 배열에 개수를 저장한다.

마지막으로 배열을 순회하면서 개수만큰 해당 인덱스를 링크드 리스트에 넣는 방법으로 구현했다.

이런식으로 시간복잡도 O(N)에 풀 수 있는 방법을 생각해냈다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 결과 저장할 ListNode
        ListNode head = new ListNode();
        ListNode node = head;

        // 숫자 개수를 저장할 배열
        int[] result = new int[20005];

        for(int i = 0; i < lists.length; i++)
        {
            while(lists[i] != null)
            {
                // 10000을 더하는 이유는 -10000까지 값이 있기 때문
                result[10000 + lists[i].val]++;

                lists[i] = lists[i].next;
            }
        }

        // 인덱스에 해당하는 숫자의 개수만큼 링크드 리스트에 넣어준다.
        for(int i = 0; i < result.length; i++)
        {
            while(result[i] > 0)
            {
                node.next = new ListNode();

                node = node.next;

                node.val = i - 10000;

                result[i]--;
            }
        }

        // 처음 노드에는 아무 값도 안넣는 식으로 구현했기 때문에 next를 리턴한다.
        return head.next;
    }
}

제출 화면

오늘은 hard 문제라서 순간 겁을 먹었던 문제였다.

다행히 제약조건이 깐깐한 편이 아니라서 그나마 쉽게 풀 수 있었던 것 같다.

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

2022년 2월 04일 금요일 - 와 2일 일하고 쉰다!

오늘 올려볼 문제는 525번 Contiguous Array 이라는 문제이다.

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

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

오늘 회사에서 1시간 동안 휴게실에 있는 물품을 날랐다. 힘드러따..

입력

사진에서도 볼 수 있듯이 0과 1 로만 이루어진 int 배열 하나를 입력받는다.

풀이 및 코드

0과 1로만 이루어진 배열의 부분배열 중 0과 1의 개수가 같으면서 가장 긴 부분배열의 길이를 구하는 문제이다.

처음에는 포인터 2개를 만들어 배열 양쪽 끝에 하나씩 두어 0과 1중 더 많은 것을 빼는 방법으로 구현하려 했다.

하지만 왜인지 통과하지 못하는 테스트케이스들이 있었다.

그래서 다른 방법을 찾아보았다.

그래서 생각한 방법은 hashmap과 dp라면 dp를 활용하는 것이다.

누적된 합을 저장하는 변수에 0이라면 -1을 1이라면 1을 더한다.

더한 후 hashmap에 이를 키값으로 가지는 값이 있는지 보고 없다면 해쉬맵에 넣는다. (해쉬맵에 들어간 value는 index이고 해당 키값을 가지는 값들 중 가장 왼쪽에 해당하는 index가 들어간다.)

키값으로 가지는 값이 있다면 현재 index와 hashmap에 저장된 index와의 차이를 구하고 max 값과 비교하여 update 한다.

이런식으로 시간복잡도 O(N)에 풀 수 있는 방법을 생각해냈다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findMaxLength(int[] nums) {
        int max = 0, num = 0;

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);

        for(int i = 0; i < nums.length; i++)
        {
            // 0이라면 -1을, 1이라면 1을 더한다.
            num += (nums[i] == 1 ? 1 : -1);

            // num에 해당하는 키 값이 없다면 index를 넣어준다
            if(!map.containsKey(num))
                map.put(num, i);
            // num에 해당하는 키 값이 있다면 hashmap에 저장된 index와 현재 index를 비교하여 max값을 갱신한다.
            else
                max = Math.max(max, i - map.get(num));
        }

        return max;
    }
}

제출 화면

오늘은 푸는 데 굉장히 많은 시행착오를 겪은 문제였다.

포기할까 생각도 했지만 그래도 "풀 수 있을 것 같다"라는 생각 덕분에 풀 수 있었던 것 같다.

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