[Hashing][Medium] 128. Longest Consecutive Sequence

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

 

 

Q. 정렬되지 않은 정수 배열 nums가 주어질 때, 연속된 숫자들의 최대 길이를 구하라. 

 이때 Time Complexity 가 O(N) 이 되도록 알고리즘을 작성하라. 

 

 

Solution. 

 TC가 O(N)이 되야 하므로, 정렬은 쓰면 안되는 것이다. 

 map이나 set에 넣는 것도 넣을 때 log(N), 이것을 모든 원소들에 대해 수행 주고 찾고 해야 하므로, 결국 Nxlog(N)이 걸리므로, 역시 쓰면 안되는 것이다. 

 

 그렇다면 hash 정도 쓰면 되는 것인데, c++ 에서는 unordered_map, unordered_set 을 쓰면 배열처럼 O(1)에 데이터 접근이 가능하다.

 그렇다고 이것들이 정렬을 해 주는 것은 아니므로, 연속된 숫자를 찾는 로직을 생각해 보면, 

 

 배열 값 nums를 unordered_set에 넣는다. 

 정렬되지는 않지만, 유일한 값들만 해당 set에 O(N)으로 들어간다. 

 

  다시 nums array를 순회하면서, 해당 값 - 1이 set에 있는지 찾아본다. 

  없다면 현재값이 nums array에서 연속되는 값 중 시작하는 값이라 할 수 있으므로, 여기서 부터 몇개의 연속된 수가 존재하는지 센다. 

  그 개수 중 최대값이 결과가 된다. 

  이것이 전체 TC O(N)을 만족하는지 다시 한번 생각해 보자. 

 

  inner loop에서 연속된 수를 시작부터 찾을때, 다음 루프에서 같은 조건에 이 수들을 다시 순회하는가?

 그렇지 않다. 연속된 수들은 해당 수 - 1 이 set에 존재하게 되므로, inner loop로 들어오지 않게 되고, 따라서 inner loop를 최종 N 번만 될게 된다. (매번 N돌게 되면 O(NxN) 이 되므로 실패. )

  따라서 전체적으로 O(N)이 된다고 간주 할 수 있다. 

 

int longestConsecutive(vector<int>& nums) 
{
    if(nums.size() <= 1)    return nums.size();

    unordered_set<int> setBuff;
    for(int k = 0; k < nums.size(); ++k)
    {
        if(setBuff.find(nums[k]) == setBuff.end())
            setBuff.insert(nums[k]);
    }

    int maxLen = 0;
    unordered_set<int>::iterator it = setBuff.begin();
    // nums array loop를 돌 수도 있지만, 그렇다면 중복값을 처리 할 수도 있으므로, 
    // 중복되지 않은 값만 있는 set만 iteration 한다.
    for(; it != setBuff.end(); ++it)
    {
        int value = *it;
        
        // 연속되지 않는 수만 inner loop로 들어간다.
        if(setBuff.find(value-1) == setBuff.end())
        {
            int start = value;
            for(int q = 1; q <= nums.size(); ++q)
            {
                // 이 조건을 만족했다면, 다시 이 inner loop로 들어오지 않게 된다.
                if(setBuff.find(start+q) == setBuff.end())
                {
                    maxLen = max(maxLen, q);
                    break;
                }
            }
        }
    }
    return maxLen;
}

 

 

적절한 결과를 얻었다.

 

 

Note) 이 문제의 핵심은 카운팅 시작 지점, value-1 이 hashSet에 존재하는지 찾는 것이다. 

c#으로 다시 풀어봄.

public int LongestConsecutive(int[] nums) 
{
    HashSet<int> buff = new HashSet<int>();
    for(int q = 0; q < nums.Length; ++q)
    {
        if(!buff.Contains(nums[q]))
            buff.Add(nums[q]);
    }

    int len = 0;
    foreach(var value in buff)
    {
        if(!buff.Contains(value-1))
        {
            int cnt = 1;
            for(int q = 1; q < nums.Length; ++q)
            {
                if(buff.Contains(value+q))
                    ++cnt;
                else break;
            }
            len = Math.Max(len, cnt);
        }
    }
    return len;
}