[ leetcode ] 128. Longest Consecutive Sequence

해당 문제는 숫자로 이루어진 배열에서, 순서와 상관없이 배열 내 숫자 중 연속되어 증가하는 숫자들이 존재하는 것들 중 가장 긴 길이를 반환하는 문제입니다.

예를 들면 [100, 4, 200, 1, 3, 2]의 배열에서는 1,2,3,4가 연속하며 증가하는 가장 긴 숫자들이므로 4가 정답입니다.

이 문제를 해결하기 위해서는 우선 배열을 오름차순으로 정렬하고 나서 보면 연속되는 부분 배열들을 살펴보면 1,2,3,4와 100 그리고 200 이렇게 세 부분 배열로 나눌 수 있습니다.

이 경우에 각 시작점의 특징은 해당 숫자보다 -1인 숫자가 배열 내에 존재하지 않는다는 특징이 있습니다.

그래서 -1인 숫자가 배열에 존재하지 않으면 시작점으로 판단하고 하나씩 증가시키며 배열에 존재할 때까지의 길이를 비교하며 제일 긴 길이를 반환하면 되는 문제입니다.

배열의 숫자들을 모두 set자료 구조에 넣고, for문으로 배열을 순회하면서 해당 숫자 -1이 없으면 시작점이라고 판단하여 set에 해당 숫자에서 +1씩하며 존재하는지 판단하여 길이를 구합니다.

#include <set>
#define max(a, b)((a) > (b) ? (a) : (b))

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        set<int> numSet(nums.begin(), nums.end());
        int answer = 0;
        for (auto num : nums) {
            if (!numSet.count(num - 1)) {
                int length = 0;
                while (numSet.count(num + length)) length++;
                answer = max(answer, length);
            } 
        }
        return answer;
    }
};