hashtabl (1) 썸네일형 리스트형 [Leetcode] 128번 - 가장 긴 연속하는 수의 개수 1. 문제 파악문제 링크: https://leetcode.com/problems/longest-consecutive-sequence문제 요구사항: 주어진 배열에서 연속된 요소의 개수를 세서 반환해라시간복잡도: O(N) 내에 풀라고 명시 -> 정렬 알고리즘은 못쓴다. 2. 핵심 문제 풀이 도출 일단, O(N) 내에 풀라고 명시했기 때문에, O(NlogN)인 정렬 알고리즘은 못쓴다. 배열을 한 번 순회하면서 연속된 수 체크해야한다. 그렇다면 정렬 없이 빠르게 값의 포함 여부를 확인하는 자료구조가 필요하다. HashTable 자료구조를 기반으로 하는 HashSet이나 HashMap 자료구조는 평균 O(1) 내에 가능하다. 따라서 해당 자료구조로 문제 풀이를 접근해본다. 배열을 순회해서 저장한 HashTable.. 이전 1 다음