[Leet code] Longest Consecutive Sequence [정렬을 이용한 풀이]

문제 링크

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

문제 이해

• 여러 정수들을 포함하는 "정렬되지 않은" 배열이 주어진다.
• 이때 연속된 수들 중 가장 긴 것의 갯수를 반환하면 되는 문제이다.
• 그리고 두 번째 입출력 예시를 보면, 중복값은 제거한 채 실행되는 것을 확인 가능하다.
• 그리고 입력값의 최소값은 0이기 때문에, 이 경우의 예외처리도 고려한다.

접근 방법

• 직관적으로 생각해보면, 배열을 순회하며 한 정수를 기준으로 추가적으로 다음 연속되는 수가 있는지를 while 문을 통해서 연속되는 수가 더 이상 없을 때까지 검사하면 되는 문제이다.
• 하지만 제한 조건을 살펴보면, 최대 입력값이 10^5이다. 즉 O(N^2)이하의 시간복잡도로 해결해야 시간 초과가 발생하지 않을 것이다.
• 따라서 다른 방법을 생각해보아야 한다. 크게 두 가지 방법이 존재하는데, 주어진 배열을 정렬(O(NlogN)해서 연속되는 정수들의 갯수를 구하거나, 해쉬테이블을 이용하여 연속되는 정수를 찾는 과정을 O(1)로 낮추는 방법을 생각할 수 있다.
• 이번 포스트에서는 정렬을 이용하여 풀이한 과정을 작성한다.

코드 설계

• 먼저 배열을 정렬한 뒤, 중복값을 제거한다.
• for 문을 통해 순회하며, 기준 정수 다음으로 연속되는 수가 나타나는지 검사한다.
• 연속되는 수인 경우, 갯수를 count에 갱신하고, 기존 answer 값과 비교하여 더 크면, answer에 갱신한다.
• 그리고 연속이 종료되는 시점부터 다음 순회가 이어지도록 해야한다. 연속성 검사가 중복으로 시행될 수 있기 때문이다.(시작점부터 검사하는 것이 훨씬 효율적이다.)

코드 구현

const longestConsecutive = function(nums) {
    if(nums.length === 0) return 0
   
    let answer = 0
    nums = nums.sort((a, b) => a - b)   // O(nlogn)
    nums = [...new Set(nums)]
    for(let i = 0; i < nums.length; i++) {
        let count = 1
        let currentIndex = i
        let currentValue = nums[i]
        while(1) {
            currentIndex += 1
            if(nums[currentIndex] - 1 === currentValue) {
                count += 1
                currentValue += 1
            }
            else {
                if(count > answer) answer = count
                i = currentIndex-1
                break;
            }
        }
    }
    return answer
};