ps:problems:leetcode:128
Longest Consecutive Sequence
| ps | |
|---|---|
| 링크 | leetcode.com/… |
| 출처 | LeetCode |
| 문제 번호 | 128 |
| 문제명 | Longest Consecutive Sequence |
| 레벨 | Medium |
| 분류 |
기본 |
| 시간복잡도 | O(n) |
| 인풋사이즈 | n<=10^5 |
| 사용한 언어 | python 3.14 |
| 제출기록 | 36.68MB / 53ms |
| 최고기록 | 0ms |
| 해결날짜 | 2026/05/16 |
풀이
- 먼저 정렬을 해두면 연속되는 시퀀스를 구하는 것은 매우 간단한데, 문제에서의 요구사항은 O(n)에 풀라는 것이기 때문에 정렬을 사용할 수 없다.
- 이 경우에는, 연속되는 시퀀스의 원소들은 {값}-{인덱스} 가 일정하다는 것을 이용하면 한층 더 간결하게 쓸수있다.
- 생각보다 발상이 즉각적으로 떠오르지 않는데, 이것은 정답이 어려운 아이디어를 사용해서라기 보다는, 보통 이러한 태스크는 그냥 정렬해서 처리하는게 실제 실행속도에서는 별로 불리함이 없었을 것이기 때문이다. 저 차이로 풀이의 통과 여부가 달라지려면 n이 상당히 커져야 할텐데, 문제 세팅이 어려울 것 같다.
- 이 문제에서도 정렬기반의 풀이가 딱히 더 느리게 동작하지 않는다. 아래 첨부한 두 코드중에서, 정렬 기반의 방법은 44ms로 오히려 더 빨리 돌았다. 두 코드 모두 최적화가 빡세게 된 것은 아니라는 것을 감안해도 별 차이가 없다고 생각해도 될것이다..
- 암튼, 정해는 해시셋을 이용하는 방법이다. 모든 수를 해시셋에 저장해두면, 어떤 수 x가 연속된 시퀀스의 첫번째가 될수 있을지의 여부를 x-1이 셋이 존재하는지를 확인하는 방법으로 O(1)에 찾을수 있다. 이렇게 연속된 시퀀스의 첫번째가 되는 수들에 대해서, x+1, x+2, … 이 셋 안에 들어있는지를 확인하면, 각각의 시퀀스의 길이를 구할수 있다. 시간복잡도는 O(n)
- 이 방법 말고 dsu를 사용하는 O(n)방법도 존재한다. 이 방법은 좀더 복잡하고 느리지만, 오히려 정해보다도 알아두어야 할 가치가 있는데, 수들이 온라인으로 들어와서 진짜로 정렬을 사용하기 불가능한 상황에서도 사용가능한 방법이기 때문이다. 해시셋과 Disjoint set을 이용해서, 이전에 추가된적이 없었던 x가 추가되면, x+1과 x-1이 이전에 추가되었는지를 확인하고, 추가된 적이 있다면, x와 x-1, x와 x+1을 유니온해주는 방식으로 처리해준다. 코드는 생략
코드
정해 O(n)
정렬 기반 - O(nlogn)
ps/problems/leetcode/128.txt · 마지막으로 수정됨: 2026/05/16 06:19 저자 teferi
토론