[Leet code] Longest Consecutive Sequence [해쉬테이블을 이용한 풀이]

문제 링크

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

문제 이해

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

접근 방법

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

코드 설계

• 주어진 nums를 순회하며, Set을 이용하여 중복값을 제외한 데이터 컬렉션을 만든다.
• 컬렉션 내 저장된 정수들을 순회하며, 순회된 요소를 기준으로 하나씩 더한 값이 연속으로 나타나는지를 while문 내부에서 찾는다. 이때 count는 하나씩 늘려가면서 찾는다.
• 이때, 연속으로 나타나는 리스트의 시작점인 정수에 대해서만 두번째 과정을 수행해야한다. 만약 모든 정수에 대해서 위 과정을 수행하게 되면 O(N^2)의 시간복잡도를 가지게 되지만, 시작점인 경우에 대해서만 수행하면 중복되는 리스트는 모두 건너뛰기 때문에 최종적으로 O(N)의 시간복잡도를 가지게 되므로 문제 조건을 만족한다.

코드 구현

const longestConsecutive = function(nums) {
    if(nums.length === 0) {
        return 0
    }
    let answer = 0
    const hashMap = new Set()
    for(let i = 0; i < nums.length; i++) {
        hashMap.add(nums[i])
    }
    
    for(const num of hashMap) {
        let count = 1
        let currentValue = num
        if(hashMap.has(currentValue - 1)) {
            continue
        }
        while(true) {
           currentValue += 1
           if(hashMap.has(currentValue)) {
               count += 1
           }
           else {
               if(count > answer) {
                   answer = count
               }
               break;
           }
        }
    }
    return answer
};

번외

• 해쉬테이블을 사용하였기 때문에, 메모리를 더 소모할 것이라 생각하였다.
• 리트코드에서 정렬방법과 메모리 소모량을 비교해보았지만, 두 경우 모두 62~64MB 내외로 큰 차이는 나지 않았다.
• 초기에 반복문을 for문 내부에 i 변수로 선언하는 방식에서 for of 문 방식으로 변경하였는데, runtime이 254ms에서 100ms로 줄었다.
• for of 방법이 좀 더 빠를 것이라 생각되어 여러 자료들을 찾아보았지만, 두 방법의 성능 차이는 실행 및 다른 조건에 따라 달라질 수 있다고 한다.

참고

• for i 방식은, 인덱스 값을 사용하여 배열의 요소에 직접 접근하는 방법이고, for of 방식은 배열 또는 이터레이블 객체를 순회하는 방법이다.