[leetcode] 128.Longest Consecutive Sequence [kotlin]

문제 분석

1. sorting 되지 않은 array가 input으로 주어진다.

2. 연속된 숫자들이 가장 긴 경우의 숫자를 파악해야되는 문제이다.

3. 시간복잡도 제한은 O(n)이다.

 

문제 해결

1. sortedSet을 사용했다.

2. sortedSet의 정렬은 logN이 걸리기 때문에, sortedSet을 사용했다.

3. 각 숫자들을 정렬한다음. 현재 숫자와 앞의 숫자와 비교하여, 길이를 계산하였다.

    - 가장 첫번째의 경우 다음 숫자를 null로 두어, null 일 경우에는 첫번째 숫자로 가정하여 길이만 더하고, 다음 숫자를 (현재 숫자 + 1)로 지정하였다.

4. 마지막 순회는 O(n)이기 때문에 O(n) 시간복잡도 이내에 문제를 해결할 수 있다.

 

class Solution {
    fun longestConsecutive(nums: IntArray): Int {
        val numbers = sortedSetOf<Int>()
        for (n in nums) {
            numbers.add(n)
        }
        var nextNum: Int? = null
        var consecutiveCnt = 0
        var tmp = 0
        for (n in numbers) {
            if (nextNum == null) {
                nextNum = n + 1
                tmp = 1
                consecutiveCnt = maxOf(consecutiveCnt, tmp)
                continue
            } else {
                if(nextNum == n) {
                    nextNum = n + 1
                    tmp += 1
                    consecutiveCnt = maxOf(consecutiveCnt, tmp)
                } else {
                    nextNum = n + 1
                    tmp = 1
                }
            }
        }
        return consecutiveCnt
    }
}

/**
sorting 되지 않는 어레이에서 가장 긴 연속되는 값을 구해라.
한번만 돌아야되고, 
 */