이 코드는 이미 정렬된 배열에서 첫 번째 값을 찾으려고 할 때 아주 비효율적으로 동작합니다. 아직 이런 데이터가 없었다는 것이 놀랍네요.
이런 상황을 방지하기 위해 보통 중간값에 가까운 값을 찾아서 피벗으로 잡거나 아예 배열을 랜덤하게 섞는 등의 방법을 사용합니다.
11004번 - K번째 수
이 코드는 이미 정렬된 배열에서 첫 번째 값을 찾으려고 할 때 아주 비효율적으로 동작합니다. 아직 이런 데이터가 없었다는 것이 놀랍네요.
이런 상황을 방지하기 위해 보통 중간값에 가까운 값을 찾아서 피벗으로 잡거나 아예 배열을 랜덤하게 섞는 등의 방법을 사용합니다.
댓글을 작성하려면 로그인해야 합니다.
lsh9034 5년 전
quick selection인가요? 퀵소트를 응용한 셀렉션을 그대로 구현해서 풀긴했는데요. 다른 분들 소스를 보니까 nth_element() ?이거를 쓰셔서 풀었는데 검색해보니까 퀵 셀렉션이더라구요. 아무리 라이브러리 함수라지만 10배 이상 차이가 나는건 좀 의문이 들어서요.. 제 코드는 1260ms인데 다른 분들을 막 100ms... 제 코드의 어디가 문제가 있는건지 질문드립니당.. ㅠㅠ