Blind 75 Must do Leetcode: Longest Consecutive Sequence

Blind75는 Leetcode의 문제들 중 소프트웨어 엔지니어 인터뷰 준비에 유용한 75개의 문제를 선정한 것을 말한다. Blind75는 배열, 문자열, 링크드 리스트, 트리, 그래프, 정렬, 다이나믹 프로그래밍 등 다양한 알고리즘과 자료구조를 포함하고 있다. 따라서 이 목록은 인터뷰 준비를 체계적으로 하고자 하는 사람들에게 방향을 제시해 주며, 실제 인터뷰에서 자주 출제되는 유형의 문제들을 연습할 수 있게 해 준다.

 

Blind 75 문제를 하루에 한 문제씩 풀어보면서 코딩 테스트 감을 유지해보려고 한다. Blind 75 풀어보기 시리즈 두번째 문제는 Longest Consecutive Sequence다. 

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

LeetCode - The World's Leading Online Programming Learning Platform

정렬되지 않은 배열에서 연속으로 나오는 숫자의 배열 중 가장 긴 것의 길이를 찾는 것이 문제다. (한글로 번역하니 참 어렵다) 추가적인 제약 조건으로 시간 복잡도가 O(n)인 알고리즘을 구현해야 한다. 즉, 배열을 정렬하고 배열의 원소를 차례대로 카운트하는 방법은 생각할 수 없다.

1. HashSet을 사용하여 배열의 원소 저장: 먼저 배열을 살펴보고 각 원소를 HashSet에 저장한다. 이 단계를 통해 O(1) 시간에 숫자가 존재하는지 확인할 수 있습니다.
2. 수열 찾기 시작점: HashSet을 순회하면서, 각 수에 대해 수열의 시작인지 확인한다. 수열의 시작점은 수열 직전의 수 (n - 1)가 HashSet에 없으면 수열의 시작점이다.
3. 수열의 길이 세기: 찾은 각 시작점에 대해 수열의 길이를 세어본다. 다음 연속된 숫자(숫자 + 1, 숫자 + 2 등)가 HashSet에 포함되어 있는지 계속 확인하면서 길이를 증가시킨다.
4. 수열의 최대 길이 추적하기: 이 프로세스 중에 발견된 최대 수열 길이를 업데이트한다.

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for(int num : nums) {
            numSet.add(num);
        }
        int longestStreak = 0;
        for(int num : numSet) {
            if (!numSet.contains(num-1)) {
                // sequence start
                int currentStreak = 1;
                int currNum = num;
                while(numSet.contains(currNum + 1)) {
                    currentStreak++;
                    currNum++;
                }
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }
}

시간 복잡도를 분석해보자.

nums 배열의 크기를 n이라고 할 때, HashSet을 생성하고 배열의 원소를 추가하는 데에 O(n) 시간이 필요하다.

다음은 numSet을 순회하면서 시퀀스의 길이를 확인하는 루프다. for 루프 안에 또 while문이 있어서 O(n^2)인 알고리즘으로 보일 수 있다. 하지만 내부의 while 루프의 경우, num이 수열의 시작(첫 번째 원소) 일 때만 실행되기 때문에 연속적인 숫자는 딱 한 번만 방문한다. 그리고 수열의 시작이 아닌 경우 한 번씩 방문하기 때문에 O(n) + O(n) = O(n)이다.

그래서 최종적인 시간 복잡도는 O(n) + O(n) = O(n)이다.

 

이 블로그의 다른 Blind75 풀이는 https://codeendeavor.tistory.com/tag/blind75 에서 확인할 수 있다.