(Leetcode) 128 - Longest Consecutive Sequence

기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.

https://neetcode.io/practice

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

문제에 O(n)으로 풀어달라고 명시되어있다.

내가 작성한 풀이

처음에 봤을 때 어떻게 O(n)으로 풀지 라는 생각을 했었는데, Arrays.sort를 사용하지 말고 풀어보자고 다짐하면서 코드를 작성해나갔다.

작성한 코드를 submit 하니 통과는 하였다. 하지만 코드를 분석해보았는데 결국은 sort를 사용한 것과 다름이 없는 코드였다. (min heap 을 사용했다.)

그래서 도대체 사람들이 어떻게 풀었을까 코드를 확인해봤는데 결국 sort를 쓴 코드가 대다수였다.

그리고 아래의 재밌는 방법이 보였다.

모범답안 - hashset 사용

진짜 재밌었던 풀이 방식이였다.

문제에 Hash Table 이라는 라벨이 달려있어서, HashSet이나 HashMap을 쓴 방법이 있을 것이라 생각하였는데 막상 연결을 못했었었다.

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();

    for(int num : nums) {
        set.add(num);
    }

    int max = 0;
    for(int num : set) {
        if (!set.contains(num - 1)) {
            int current = 1;
            while (set.contains(num + 1)) {
                current++;
                num++;
            }
            max = Math.max(current, max);
        }
    }

    return max;
}

set은 정렬되어 있지 않다. 따라서 어떤것부터 iterate를 할 지는 알 수 없다.

hash set의 search는 O(1)이다. set.contains(num - 1) 를 확인하는 이유는 해당 값이 있을 경우 연속된 값 중 맨 좌측에 있는 값이 아니기 때문이다. 만약 맨 좌측에 있는 값이라면 1씩 더해가면서 어디까지 있는지 확인한다. (set.contains(num + 1)). 연결이 종료되면 해당 길이를 max에 기록한다.

TC, SC

시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다.