[문제 링크]
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;
}
}
[회고]
처음엔 막막했지만 하나하나 생각하며 풀어보니 풀렸다.
하나의 유형을 더 알게된 것 같아서 좋다.
질문과 피드백은 언제나 환영입니다.
감사합니다.
'CodingTest > LeetCode' 카테고리의 다른 글
[LeetCode] 104. Maximum Depth of Binary Tree (0) | 2025.03.18 |
---|---|
[LeetCode] 2895. Minimum Processing Time (0) | 2025.03.16 |
[LeetCode] 503. Next Greater Element II (0) | 2025.03.13 |
[LeetCode] 3184. Count Pairs That Form a Complete Day I (0) | 2025.03.13 |
[LeetCode] 2848. Points That Intersect With Cars (0) | 2025.03.12 |