aod0326   3년 전

퀵소트 방식으로 해서 중간에 K번째 수를 찾았으면

출력하고 flag를 false로 바꿔서 나머지 재귀 함수들이 다 실행되지 않도록 했습니다..

그리고 pivot과 찾고하자는 K를 비교해서 K가 pivot보다 크면 그에 해당하는 재귀함수만 실행하고

다른거는 수행안하도록 했구요..

(아래 코드 보시면 아시겠지만) random함수로 n에 500만, k에 500만 혹은 아무 수 넣고 시간 측정해봤는데

1초도 안나옵니다.. 근데 2%에서 시간초과가 나네요 ㅠㅠ 중간에 논리적으로 틀린 부분이 있는지 먼지 몰겠어요

10번정도 시도했는데 다 시간초과네요 ㅠㅠ 

고수분들 도와주시면 감사하겠습니다! ㅠㅠ

bupjae   3년 전

pivot 를 start 점으로 하셨는데, 이 경우 배열이 이미 정렬 (또는 역정렬) 되어 있을 경우 효율이 매우 떨어집니다.

aod0326   3년 전

백준님 퀵소트 소스가 pivot을 중앙에 잡은거라서 그대로 써서 해봤는데도

2%에서 멈추네요....................................................................ㅠㅠㅠㅠㅠ

뭘 건드려야 대는지 모르겠어요 ㅠㅠ

aod0326   3년 전

아.... 500만개 숫자 입력받는게 문제였네요..

in.readLine().split(" ");해서 받았는데 이게 문제였어요..

StringTokenizer로 하니까

그냥 Arrays.sort()하고나서 k번째꺼 출력해도 시간안에 출력되네요...

이런 허무한..

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