Longest Consecutive Sequence

오랜만에 리트코드 문제를 풀어봤다. 추천 문제들을 다 풀어보는게 목표이고 천천히 하면 좋을거같다.

이 문제는 숫자가 순차적으로 나열된 최대 길이를 반환해야 하는 문제인데 조금 어렵게 나온건 O(n) 시간으로 풀어야 한다는 것이었다.

Sort() 같은 함수는 사용하면 안되기에 Map으로만 풀었고, 바로 전에 있었던 숫자가 나타난 횟수를 증가 시킴으로서 한번에 탐색에 가장 긴 sequence 를 찾을 수 있었다.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int answer = 0; 
        map<int,int> hashMap; 
        
        for(int n : nums){
            if(!hashMap.count(n)) hashMap[n]++; 
        }

        for(auto& it : hashMap){
            if(hashMap.count(it.first - 1)){
                hashMap[it.first]+=hashMap[it.first-1]; 
            }
        }

        for(auto& it : hashMap){
            answer = max(answer, it.second); 
        }

        
        
        return answer; 
    }
};