(Graph, Medium) Longest Consecutive Sequence

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

이걸 왜 그래프로 분류했는지 모르겠다, n+1이나 n-1에 대해 노드를 연결하나..?
어쨌든 문제에서는 O(n) 시간복잡도로 풀라고 지시한다.

우선 간단하게 생각하면 특정 숫자를 콕 찝어서 while로 -1 동안 계속 존재하는지, +1동안 계속 존재하는지 볼 수 있겠다.

1안 - 시간 제한 초과

처음 생각한 아이디어대로 특정 숫자 기준 왼쪽 오른쪽 -1, +1 모두 탐색하여 max 길이를 구하는 로직.
submit 시 시간 제한에 걸린다. 최적화가 필요함

import java.util.*;
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            set.add(n);
        }

        int maxLength = 0;

        for (int n : nums) {
            int length = 1;
            int temp = n;
            while (set.contains(temp - 1)) {
                temp--;
                length++;
            }

            temp = n;
            while (set.contains(temp + 1)) {
                temp++;
                length++;
            }

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

        return maxLength;
    }
}

2안 - 통과하나 최적화 여지 있음

-1, +1 탐색 시 set에서 지워주는 로직만 추가되었다.
시작점이 어디든 이어져있으면 한 번의 체크에서 모두 수행할 수 있다.
결국에는 while문을 타고 그 요소까지 닿을 수 있기 때문.

1안에서는 set에서 remove를 하지 않고 있었는데, 그러면 똑같은 시퀀스를 계속 체크하고 있는 셈이 된다.
그러므로 중복 제거를 위해서는 -1, +1 탐색 시 해당 요소를 지워준다.

통과 되긴 하는데, 런타임이나 메모리 모두 다른 사람들의 풀이에 비해 많이 씀

import java.util.*;
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            set.add(n);
        }

        int maxLength = 0;

        for (int n : nums) {
            int length = 1;
            int temp = n;
            while (set.contains(temp - 1)) {
                temp--;
                length++;
                set.remove(temp);
            }

            temp = n;
            while (set.contains(temp + 1)) {
                temp++;
                length++;
                set.remove(temp);
            }

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

        return maxLength;
    }
}

3안 - 최적화

이건 몰라서 GPT 참고했다.
애초에 -1이 안 찾아지는 곳부터 시작해서 오른쪽(+1)만 보면 되는구나.

import java.util.*;
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int maxLen = 0;

        for (int num : numSet) {
            // 시작점인지 확인
            if (!numSet.contains(num - 1)) {
                int currNum = num;
                int length = 1;

                // 다음 숫자 연속 확인
                while (numSet.contains(currNum + 1)) {
                    currNum++;
                    length++;
                }

                maxLen = Math.max(maxLen, length);
            }
        }

        return maxLen;
    }
}