[Leetcode Top Interview 150] 128. Longest Consecutive Sequence

난이도 : medium

문제링크

• 정렬되어지지 않은 정수형 배열 nums가 주어진다
• 가장 긴 연속적인 요소들의 길이를 리턴하라
• ex) [100,4,200,1,3,2] => 4 (1, 2, 3, 4)

 

1. 접근법

• 해시테이블에 요소별 인덱스 Entry를 저장함
• 방문용 set을 선언함
• 요소를 하나하나 순회하면서,
  • 현재 탐색중인 원소보다 1 더 크고 방문하지 않았으면, 길이를 1 늘려 반복한다
  • 현재 탐색중인 원소보다 1 더 작고 방문하지 않았으면, 길이를 1 줄여 반복한다
• 길이와 최종 답의 max값을 최종 답으로 업데이트한다

 

3. 구현 코드

public int longestConsecutive(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }

    // val - idx
    Map<Integer, Integer> map = new HashMap<>();
    Set<Integer> visited = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(Integer.valueOf(nums[i]), Integer.valueOf(i));
    }

    int ans = 1, length;
    for (Integer num : map.keySet()) {
        length = 1;
        num = Integer.valueOf(num+1);
        while (map.containsKey(num) && !visited.contains(num)) {
            visited.add(num);
            num = Integer.valueOf(num+1);
            length++;
        }

        ans = Math.max(ans, length);
    }

    visited = new HashSet<>();
    for (Integer num : map.keySet()) {
        length = 1;
        num = Integer.valueOf(num-1);
        while (map.containsKey(num) && !visited.contains(num)) {
            visited.add(num);
            length++;
            num = Integer.valueOf(num-1);
        }

        ans = Math.max(ans, length);
    }

    return ans;
}

• 시간초과로 실패하였다

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 데이터를 순회함
• 공간복잡도 : O(n) - 모든 데이터를 생성해야 함

 

5. 개선점

• 시간복잡도에서 중복적으로 탐색하는 부분이 많다

 

6. 회고

• 어떻게 하면 시간복잡도를 줄일지 모르겠어서 강의를 들었다

public int solutionLongestConsecutive(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }

    Set<Integer> set = new HashSet<>(Arrays.stream(nums).boxed().collect(Collectors.toList()));
    int ans = 0;
    for (int num : nums) {
        if (!set.contains(num-1))  {
            int length = 0;
            while (set.contains(num + length)) {
                length++;
            }
            ans = Math.max(ans, length);
        }
    }

    return ans;
}

(출처 : NeetCode)

• nums를 모두 set에 집어넣는다
• nums를 순회하면서
  • 현재 방문한 num값이 연속적인 시퀀스의 첫번째 원소가 아니라면 -> 가장 긴 시퀀스가 될 가능성이 없으므로 패스함
  • 현재 방문한 num값이 연속적인 시퀀스의 첫번째 원소라면 -> 오름차순 시퀀스 길이를 계산하여 최대길이 갱신을 위해 비교함
  • 오름차순과 내림차순의 길이가 동일하므로, 방향은 정하면 된다

 

• 이렇게 하면 한번의 배열 순회로 문제를 풀 수 있다..!!