.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
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.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is[1, 2, 3, 4]. Therefore its length is 4.
Plain Text
복사
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Plain Text
복사
Constraints:
•
0 <= nums.length <= 10^5
•
-10^9 <= nums[i] <= 10^9
My solution
정렬되지 않은 정수 배열 nums가 주어지면 가장 긴 연속 요소 수열의 길이를 반환한다.
O(n) 시간에 실행되는 알고리즘을 작성해야 한다.
연속 요소는 어떤 요소에서 1씩 증가하는 요소를 뜻한다.
직관적으로 생각하면 브루트포스로 삼중 for문을 사용해서 구현할 수 있을 것 같다. 하지만 실행 시간에 대한 제약이 있다..
다른 방식을 생각해보니 차례대로 숫자를 나열해야 판별하기 쉬울 것이 당연하기 때문에 Sort가 필요하다 생각했다. 각 숫자를 이전 숫자 + 1이 되는지 확인하면서 그 maxNum을 업데이트하는 방식으로 하면 된다.
하지만 JavaScript의 sort 메서드는 시간 복잡도가 O(nlogn)인 것으로 알고 있어 다른 방법을 찾아야 한다고 생각해 쉽지 않았다.
중첩이 아니라 for문을 여러 번 써야하지 않을까?
먼저 nums를 처음부터 끝까지 돌면서 Set에 담아둔다. ( 요소가 겹치는 건 중복 제거를 해도 되므로 Set )
그 다음 다시 Set를 처음부터 끝까지 돌면서... sort 방식에서와 비슷하게 해당 요소보다 1 작은 요소가 존재하는지를 확인하도록 했다.
그런데, 이전 요소가 존재하지 않을 때 확인하도록 바꿔야 이미 방문하지 않은 요소를 1씩 늘려가며 검사할 수 있음을 알게 되었다.
이를 해결하기 위해 자료를 참고하면서 위의 2개의 방식도 솔루션으로 인정된다는 사실을 알게 되었지만, 해싱문제로 도전했던 것이기 때문에 마지막 방식으로 시간 복잡도를 낮추고 문제를 해결할 수가 있었다.
Code
/**
* @param {number[]} nums
* @return {number}
*/
const longestConsecutive = function (nums) {
const numSet = new Set();
for (const num of nums) {
numSet.add(num);
}
let longestLen = 0;
for (const num of numSet) {
// If the number is not in the set, it means it has not been visited yet.
if (!numSet.has(num - 1)) {
let currentNum = num;
let currentLen = 1;
// check if the next number is consecutive
while (numSet.has(currentNum + 1)) {
currentNum += 1;
currentLen += 1;
}
// update longestLen if currentLen is longer than longestLen
longestLen = Math.max(longestLen, currentLen);
}
}
return longestLen;
};
describe('longestConsecutive', () => {
it('TC1', () => {
expect(longestConsecutive([100, 4, 200, 1, 3, 2])).toStrictEqual(4);
});
it('TC2', () => {
expect(longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1])).toStrictEqual(9);
});
});
JavaScript
복사
