리트코드 스터디 1주차

 

12월 초부터 dale님이 운영하는 코딩 테스트 스터디에 참석 중이다.

 

지금이 3주차인데, 블로그를 너무 버려두고 있는 것 같아서 조금씩 다시 써보려고한다.

 

1주차 문제는 다음과 같다.

 

1. Contains Duplicate

https://leetcode.com/problems/contains-duplicate/

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> numSet = new HashSet<>();

        for (int num : nums) {
            if (numSet.contains(num)) {
                return true;
            }
            numSet.add(num);
        }

        return false;
    }
}

배열에 중복된 숫자가 존재하는지 판단하는 문제.

 

set을 사용하면 굳이 정렬을 사용할 필요가 없어서 O(N log N)이 아닌 O(N)으로 문제를 해결할 수 있다.

 

2. Valid Palindrome

https://leetcode.com/problems/valid-palindrome/

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0
        int right = s.length() - 1;

        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;

            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }
}

정규표현식으로 문자열을 제거하고 푸는게 자바에서 보이는 일반적인 풀이지만 투포인터로도 풀 수 있다.

 

개인적으로 투포인터 풀이를 좋아하기도하고 정규표현식을 싫어해서 이런저런 아이디어를 내서 푼 문제. 

 

3. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(
                Comparator.comparingInt(countMap::get).reversed()
        );

        pq.addAll(countMap.keySet());

        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = pq.poll();
        }
        return result;
    }
}

횟수를 저장하는 맵을 만들고 정렬을 해줘야한다.

 

문제는 적절한 자료구조를 사용하지 않으면 횟수 가산과 정렬을 하면서 O(N^2)이 나올 수 있다.

 

HashMap과 우선순위큐를 이용해서 시간복잡도를 최대한 줄였지만, 자바에선 어쩔 수 없는 한계가 있는 문제.

 

4. Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int maxLength = 0;

        for (int num : set) {
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int count = 1;
                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    count++;
                }

                maxLength = Math.max(maxLength, count);
            }
        }

        return maxLength;
    }
}

문제에서 그냥  "O(N)으로 풀 것"이라고 박아놨다.

 

일단 정렬을 하면 O(N log N)의 시간복잡도를 갖기 때문에 가장 쉬운 방법인 정렬을 할 수 없다.

 

그리고 가장 큰 걸림돌은 중복된 숫자다.

 

중복된 숫자를 set으로 제거해주고, 연속된 숫자에 참여한 적이 없다라는 조건을 찾은 후 연속된 수를 검증하면 된다.

 

연속된 숫자에 참여한 적이 없다라는 조건은 set.conatins(num-1)으로 판별한다. 이게 생각하기 어려웠던 아이디어.

 

미디엄 난이도 문제부터는 약간의 아이디어가 있어야 쉽게 풀리는 것 같다.

 

5. House Robber

https://leetcode.com/problems/house-robber/

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];

        int prev2 = nums[0]; // dp[i-2]
        int prev1 = Math.max(nums[0], nums[1]); // dp[i-1]
        for (int i = 2; i < nums.length; i++) {
            int current = Math.max(nums[i] + prev2, prev1);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

가장 먼저 떠오른 방식은 dp다. 실제로 첫 풀이는 dp로 풀었다. 그리고 오히려 dp로 풀면 더 쉽다.

 

하지만 공간복잡도가 무조건 N으로 나오는 단점이 생긴다.

 

그래서 공간복잡도를 줄이기 위해서 이전 숫자 두개만 기억하는 방식으로 다시 풀었다.

 

nums[i]+dp[i-2]와 dp[i-1]을 비교하는 어찌보면 가장 간단한 dp 문제다. 

 

마치며

난 기본적으로 내 기억력을 믿지 않는다.

 

이런식으로 기억하려고 리뷰를 남겨놓지 않으면, 분명히 금방 다 까먹을게 뻔하다.(남겨도 기억 못할 확률이 높다.)

 

다시 글쓰는 습관을 돌리기 위한 노력을 해야겠다.

 

공부나 외부활동을 안한 것도 아닌데 일이 바쁘니 글을 쓸 여유가 없다는 핑계가 자꾸 나온다.