리트코드 - 128. Longest Consecutive Sequence

리트코드 - 128. Longest Consecutive Sequence

출처 - https://leetcode.com/problems/longest-consecutive-sequence/

 

문제 설명

정렬되지 않은 정수 배열이 주어지면 가장 긴 연속 요소 시퀀스의 길이를 반환합니다.
O(n) 시간에 실행되는 알고리즘을 작성해야 합니다.

 

풀이코드

class Solution {
    public int longestConsecutive(int[] n) {
        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < n.length; i++) {
            set.add(n[i]);
        }
        int max = 0;

        for (int num : set) {
            if (!set.contains(num - 1)) {
                int curNum = num;
                int streak = 1;

                while (set.contains(curNum + 1)) {
                    curNum++;
                    streak++;
                }
                max = Math.max(streak, max);
            }
        }
        return max;
    }
}

코드설명

시간복잡도 O(n) 시간 내에 연속하는 가장 긴 수를 찾아야 한다.

단순히 하나씩 반복문을 돌려서 찾기엔 O(n * n)번이 걸릴 것이다.

 

그럼 Arrays.sort()를 써서 구해보는건 어떨까?

아쉽지만 Arrays.sort()의 시간복잡도는 O(n * log n) 이므로 문제에서 요구하는 O(n)조건을 벗어난다.

위 두가지에 의해 기존 배열을 사용하거나 정렬을 사용하는 것은 안된다는 결론이 나온다.

 

어떤 값에 빨리 접근하기 위해서는 Hash 함수를 사용하는 것이 빠르다.

자바에서 Hash를 사용하는 자료형의 대표적인 두가지는 Set과 Map이다.

Set은 중복을 저장하지 않는 대신 값을 순차적으로 접근하기 어려운 문제가 있고, Map에는 Key-value를 저장해야 하며 key는 hash로 접근가능하지만 value를 어떤 값으로 지정하지 않으면 쓸데 없는 메모리 낭비가 된다.

 

여기서는 Set을 사용하면 쉽게 풀릴 것 같다.

0. Set에다가 모든 값을 넣은 다음에 Set배열을 순회한다.

1. 어떤 값의 -1 한 값이 없다면 이것은 시작값이 될 수 있다.

2. 시작값(curNum)을 복사해놓고, 최대길이(streak)를 1로 지정한다.

3. while문을 돌려서 curNum을 하나씩 추가해가며 set에 있다면 streak을 1씩 더해준다.

4. 최대값(max)과 비교하여 이 값이 크다면 갱신해준다.

 

이렇게 하면 시작값이 아닌 값들을 제외하면 건너뛰면서, 동시에 최대 길이를 리턴할 수 있다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

처음에는 여러개의 배열을 생각해서 하나씩 추가하는 방법을 생각했다.

예를 들어 배열을 순회하며 현재값을 기준으로 다음값이 +1, -1이면 배열에 계속 더해주는 것이다.

문제는 끊어졌을 때이다.

 

예를 들어 4 5 1 2 3 이라고 한다면, 정답은 5일 것이다.

처음에 4를 추가하고 5는 +1 이므로 만족하여 배열에 추가된다.

다음 값은 1 이므로 만족하는 값이 아니어서 새로운 배열에 값을 추가한다. 2,3 에서는 계속 만족하므로 더해질 것이다.

 

이렇게 하면 [4, 5] , [1, 2, 3]이라는 두 개의 배열이 완성될 것이고 3을 리턴할 것인데 정답이 아니게 된다.

'이전값이 없다면 시작하는 숫자'라는 생각을 비틀어서 풀이 해답을 완성시켰다.

정리

배열에서 연속된 수를 찾을 때 set을 사용하면 편하다.