kva231   3년 전

원리는 대충 맞는 것 같은데 뭔가 사소한 요소가 틀린 것일까요??

답변 부탁드립니다!!

artichoke42   3년 전

selection sort의 worst case 시간복잡도는 O(n^2)이므로 시간초과가 나게 됩니다. 다른 정렬방법을 생각해보셔야 할 것 같습니다.

kva231   3년 전

답변 고맙습니다

근데 제가 구현하고자 하는 건 그냥 selection sort이 아니고 quick selection sort입니다.

quick selection sort는 최악의 경우에도 O(n)으로 알고 있습니다.

그래서 이 문제 풀 때 quick selection sort를 이용하라고 나와있기도 합니다..

artichoke42   3년 전

죄송합니다, 제가 quick selection sort에 대해 이해가 제대로 안 된 상태에서 답변을 남겼네요..

대신 반례를 찾은 것 같아 반례를 남깁니다.

5 4
3 2 1 5 4
answer: 4
out: -1

kva231   3년 전

오 정말 고맙습니다 ㅎㅎ

일단 그 부분은 해결했으나 이제 다른 문제가 생겼네요 ㅋㅋ

48%에서 시간초과가 발생해 버립니다 윽..

artichoke42   3년 전

출력을 아예 하지 않는 것도 시간초과 사유가 되는지는 모르겠습니다만, 다음 테스트 케이스에서 아무것도 출력이 되지 않습니다.

5 3
0 1 0 0 0

kva231   3년 전

항상 답변해주셔서 고맙습니다~

근데 새로 작성해서 올린 코드에서의 반례인가요??

다시 올린 코드로 실행할 경우 0으로 출력 되고 있습니다.

댓글을 작성하려면 로그인해야 합니다.