[leetcode] 128. Longest Consecutive Sequence

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
       int answer = 0;
        unordered_set<int> s(nums.begin(),nums.end());
        
        for(int n : nums)
        {
            if(s.find(n-1) == s.end())
            {
                int now = n;
                int matched = 1;
                
                while(s.find(now + 1) != s.end())
                {
                    now += 1;
                    matched++;
                }
                answer = max(answer, matched);
            }
        }
        return answer; 
    }
};

 

결과를 확인해보니 최적은 아닌것 같지만, 우선 set을 활용하여 간단하게 풀어보았습니다.

union-find를 구현하는 문제인데 o(n)에 구현해야되니 생각나는건 set을 활용했습니다.

 

 

지금 드는 생각으론 set을 2개를 써서 풀면 좀 더 빠를거 같습니다. 나중에 구현해봐야겠네요