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;
}
'Leetcode > Challenges' 카테고리의 다른 글
[Matrix][Medium] 240. Search a 2D Matrix II (0) | 2024.04.17 |
---|---|
[Heap][Hard] 295. Find Median From Data Stream (0) | 2024.04.06 |
[Hashing][Medium] 49. Group Anagrams (0) | 2024.04.02 |
[Greedy][Medium] 763. Partition Labels. (0) | 2024.04.01 |
[Medium] 122. Best Time to Buy and Sell Stock II (0) | 2024.03.31 |