[코딩인터뷰] LeetCode - 128. Longest Consecutive Sequence 해시테이블 사용법

안녕하세요, 여러분! 🌟 오늘은 정말 흥미진진한 코딩 문제 하나를 같이 풀어보려고 해요. 바로 "128. Longest Consecutive Sequence"라는 문제인데요, 이 문제는 코딩 테스트나 인터뷰에서 종종 나오는 중요한 문제랍니다. 😊

 

Longest Consecutive Sequence

 

---

문제 설명

먼저, 문제를 이해해 봅시다. 🧐 주어진 문제는 이렇습니다:

문제: 정렬되지 않은 정수 배열 nums가 주어질 때, 가장 긴 연속된 요소의 시퀀스 길이를 반환해야 합니다.

예를 들어, nums = [100,4,200,1,3,2]라면 가장 긴 연속된 시퀀스는 [1, 2, 3, 4]이므로 길이는 4가 됩니다. 🎉

 

릿코드 문제보러가기

---

알아야 할 개념 공부하기

이 문제를 해결하기 위해서는 해시 테이블을 사용하는 것이 핵심입니다! 해시 테이블은 데이터를 빠르게 저장하고 검색할 수 있는 자료구조로, 이 문제에서는 각 숫자의 존재 여부를 빠르게 확인하는 데 사용됩니다. 🔍

 

---

문제 풀어보기

이제 실제 코드로 문제를 풀어볼게요!

1. 해시 세트를 만들어 모든 숫자를 저장합니다.
2. 배열을 순회하면서, 현재 숫자가 연속 시퀀스의 시작점인지 확인합니다 (즉, 현재 숫자보다 하나 작은 숫자가 해시 세트에 없는 경우).
3. 연속 시퀀스를 찾으면, 해당 시퀀스의 길이를 계산합니다.
4. 모든 숫자에 대해 이 과정을 반복하고, 가장 긴 시퀀스의 길이를 반환합니다.

def longestConsecutive(nums):
    if not nums:
        return 0

    num_set = set(nums)
    longest_streak = 0

    for num in num_set:
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1

            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1

            longest_streak = max(longest_streak, current_streak)

    return longest_streak

---

우리는 "128. Longest Consecutive Sequence" 문제를 성공적으로 해결했어요. 이 문제를 통해 해시 테이블과 연속 시퀀스를 찾는 방법을 배웠습니다. 앞으로도 이런 유용한 코딩 팁과 문제 해결 방법을 블로그에 계속 공유할 예정이니, 많은 관심 부탁드립니다! 💻🚀