본문 바로가기
CodingTest/LeetCode

[LeetCode] 128. Longest Consecutive Sequence

by 창브로 2025. 3. 15.

[문제 링크]

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

 

[문제]

정렬되어 있지 않은 정수형 배열 nums가 주어진다.
nums 원소를 가지고 만들 수 있는 가장 긴 연속된 수의 갯수는 몇개인지 반환하라.

[풀이 과정]

조건을 보니 O(n^2)으로 풀면 안될 것 같아서 고민을 좀 했다.일단 문제를 보면 중복된 수를

의식하지 않아도 되는 문제였기 때문에 중복 숫자를 지우고탐색 속도도 빠른 Set에 nums배열을 담기로 했다.

 

담고 한참을 생각해보니 탐색 시간을 줄이기 위해서 이미 탐색한 부분을 또 탐색하는 행동을 막아야만 했다.

저 반복을 줄이기 위해 나는 '현재의 수 -1' 의 값이 Set에 있으면 탐색을 하지 않으면 되겠다고 생각했다.

이렇게 해서 답을 구할 수 있게 되었다.

 

[코드]

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        int answer = 0;

        // 중복이 의미 없는 문제기 떄문에 배열을 Set에 담아줌
        for(int i = 0; i < nums.length; i++) {
            numSet.add(nums[i]);
        }

        for(int num : numSet) {
            // 현재 수 보다 작은 연속된 수가 있다면 할 필요가 없다
            // 나중에 작은 수에서 할때 하던지 이미 검색을 했던 수이기 때문
            if(!numSet.contains(num-1)) {
                int addCount = 1;

                // 연속된 수가 나오지 않을때 까지 count를 해주며 탐색
                while(numSet.contains(num+addCount)) {
                    addCount++;
                }
                
                answer = Math.max(answer, addCount);
            }
        }
        return answer;
    }
}

[회고]

처음엔 막막했지만 하나하나 생각하며 풀어보니 풀렸다.

하나의 유형을 더 알게된 것 같아서 좋다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.