[Algorithm] LeetCode - Longest Consecutive Sequence

📠 문제

• Longest Consecutive Sequence
• 난이도: Medium
• 정수 배열이 주어질 때, 정렬하지 않고 가장 긴 연속 수열의 길이를 구하는 문제이다.

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.

💡 풀이

처음에 오름차순, 내림차순이 생각나기 때문에 정렬을 할 수 있는데 정렬을 하는 순간 O(nlogn)이 되어버린다. 이 문제의 핵심은 O(n)으로 푸는 것이다. (문제에서 You must write an algorithm that runs in O(n) time. 라고 나와있다)

 

생각해보면 단순하다. 왜냐하면 우선 내 맘대로 배열을 배치할 수 있으니까 순서는 상관없다 연속되는지만 파악하면 된다. 결국 현재 숫자에서 1을 더한 숫자가 있는지 없는지를 알아내면 된다! 하지만 배열이라면 숫자를 찾는데 O(n)의 시간복잡도가 추가되기 때문에 Swift의 경우 Set으로 만들어서 contains(_ :)를 활용하여 확인해주면 된다.

func longestConsecutive(_ nums: [Int]) -> Int {
    let numSet = Set(nums)
    var result = 0

    for num in numSet {
        if !numSet.contains(num - 1) {
            var currentNum = num
            var currentStreak = 1

            while numSet.contains(currentNum + 1) {
                currentNum += 1
                currentStreak += 1
            }

            result = max(result, currentStreak)
        }
    }

    return result
}