[LeetCode] 128 - Longest Consecutive Sequence

문제

• 링크: https://leetcode.com/problems/longest-consecutive-sequence/
• 난이도: Medium
• 태그: 배열, 해시 테이블
• 결과: Time: 87 ms (33.77%), Space: 104.24 MB (5.03%)

풀이

O(N log N) 풀이

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty())
        {
            return 0;
        }
        
        set<int> s(nums.begin(), nums.end());

        int ans = 0;
        int con = 1;
        int prev = 1e9 + 10;
        for (auto& e : s)
        {
            if(abs(e - prev) == 1)
            {
                con++;
            }
            else
            {
                ans = max(ans, con);
                con = 1;
            }

            prev = e;
        }

        ans = max(ans, con);
        return ans;
    }
};

set이 내부적으로 정렬된 상태를 유지하는 것을 이용했다. 이 set을 오름차순으로 순회하면서 연속된 수를 찾는 방식이다.

O(N) 풀이

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty())
        {
            return 0;
        }
        
        unordered_set<int> s;
        s.reserve(nums.size());
        s.max_load_factor(0.4f);
        s.insert(nums.begin(), nums.end());

        int ans = 0;
        for(auto& e : s)
        {
            if (s.contains(e - 1))
            {
                continue;
            }

            int con = 1;
            int num = e;
            while (true)
            {
                num++;
                if(!s.contains(num))
                {
                    break;
                }

                con++;
            }
            ans = max(ans, con);
        }

        return ans;
    }
};

실행 시간 좀 줄여보려고 s 선언 직후에 잡다한 짓을 하긴 했는데, 중요하지 않다. unordered_set으로 자료구조를 바꾸었다. 순회하면서 자기보다 1만큼 작은 수가 없으면 연속된 수열의 시작이 될 수 있는 가능성이 있는 것으로 보고, 확인을 시작한다. 이렇게하면 불필요한 정렬이 필요없어지기 때문에, O(N)으로 풀이가 가능하다.

이 포스트는 달레 스터디(1주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.