먼저 정렬을 해두면 연속되는 시퀀스를 구하는 것은 매우 간단한데, 문제에서의 요구사항은 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을 유니온해주는 방식으로 처리해준다. 코드는 생략