인프런 커뮤니티 질문&답변

안녕하세요^^

실제 코딩테스트에서 "최대 길이 연속수열"과 같은 문제는 시간복잡도가 O(n)이어야 통과가 됩니다. 일단 정렬을 하면 O(nlogn)으로 시작하기 때문에 시간초과가 날 가능성이 높습니다.

안녕하세요, 인프런 AI 인턴입니다.
님께서 질문하신 내용에 대한 답변은 문제의 크기와 정렬 알고리즘의 시간 복잡도에 따라 달라질 수 있습니다. HashSet은 일반적으로 추가, 삭제, 조회에 O(1) 시간이 걸리지만, 정렬을 위해서는 추가적으로 List나 배열로 변환 후 정렬해야 합니다.

정렬 과정에서 일반적으로 사용되는 알고리즘은 퀵정렬이나 병합정렬로, 평균적으로 O(n log n)의 시간 복잡도를 가집니다. 여기서 n은 데이터의 크기입니다. 코딩테스트 문제에서 허용하는 시간 복잡도 내에서 문제를 해결할 수 있을지 여부가 중요합니다. 대부분의 중간 규모 코딩테스트에서는 적당한 크기의 데이터(n ≤ 10^5 정도)에 대해 정렬을 포함한 알고리즘도 시간 내에 해결 가능합니다.

만약 데이터 크기가 이보다 훨씬 크거나(예: n > 10^6), 허용 시간이 매우 짧은 경우에는 정렬 과정에서 시간 초과가 발생할 수 있습니다. 이런 상황에서는 더 효율적인 자료구조 사용을 고려하거나 알고리즘을 최적화해야 할 필요가 있습니다.

실제 코딩테스트에서는 문제의 조건, 허용 시간 복잡도, 입력 데이터 크기 등을 꼼꼼히 살펴보고 문제를 풀어야 합니다.