1181번 - 단어 정렬
Merge Sort로 구현해서 문제를 풀거나 C++의 algorithm에 있는 sort 함수를 이용하면 손쉽게 풀 수 있는데
궁금해서 native quick sort 소스코드를 이용해서 풀어봤는데 시간 초과가 뜨더라고요.
이게 최악의 테스트 케이스가 적용되어서 O(n^2)가 되어서 그런 건지 제가 구현을 잘못 한 것인지 모르겠어서 질문드립니다.
최악의 케이스라는 게 다름 아닌 이미 정렬된 상태로 입력이 들어오는 것이기 때문에 naive한 퀵소트면 어느 문제든 시간 초과가 날 가능성이 매우 높습니다.
아 그렇군요! 감사합니다 문제를 풀 때 가급적이면 Native한 퀵소트는 사용하지 않는 편이 좋겠네요.
native가 아니라 naive입니다. '순진한' 이라는 뜻입니다.
아하 덕분에 헷갈렸던 것도 바로잡고 가네요 감사합니다.
직접 퀵소트를 구현해야하는 상황이라면 pivot을 잡을 때 랜덤하게 선택하시면 상당히 좋은 효과를 보실 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
daisy7024 5년 전
Merge Sort로 구현해서 문제를 풀거나 C++의 algorithm에 있는 sort 함수를 이용하면 손쉽게 풀 수 있는데
궁금해서 native quick sort 소스코드를 이용해서 풀어봤는데 시간 초과가 뜨더라고요.
이게 최악의 테스트 케이스가 적용되어서 O(n^2)가 되어서 그런 건지 제가 구현을 잘못 한 것인지 모르겠어서 질문드립니다.