[LeetCode] 128. Longest Consecutive Sequence

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

LeetCode - The World's Leading Online Programming Learning Platform

문제 유형 : 해시, 배열, (우선순위 큐..?)

문제 난이도 : Medium

 

문제

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

 

정렬되지 않은 배열 nums가 있습니다. 가장 긴 연속된 수열(1씩 증가하는)의 길이를 구하시오.

선형 시간(O(n))으로 풀어야 합니다.

 

풀이

배열을 한 번 탐색하며, 우선순위 큐에 넣는다.

우선순위 큐에서 값을 빼가며, 수열이 끊길 때까지 임시 배열에 값을 넣어봅니다.

최장 길이를 업데이트하고, 끝나면 다시 시작해봅니다.

큐가 빌 때까지 반복하면, 최장 길이를 반환합니다.

 

코드

C++

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        
        priority_queue<int, vector<int>, greater<int>> pq;
        
        for(const auto& num : nums) {
            pq.push(num);
        }

        int longest = 0;
        while(!pq.empty()) {
            vector<int> sequence;
            while(!pq.empty()) {
                if(sequence.size() == 0) {
                    sequence.push_back(pq.top());
                    pq.pop();
                    continue;
                }
                if(sequence[sequence.size()-1] == pq.top()) {
                    pq.pop();
                } else if(sequence[sequence.size()-1]+1 == pq.top()) {
                    sequence.push_back(pq.top());
                    pq.pop();
                } else {
                    break;
                }
            }
            longest = max(longest, static_cast<int>(sequence.size()));
        }
        return longest;
    }
};