답은 도출되었다. 알고리즘은 맞으시다는 거네요.
그렇지만 시간 초과가 났다.
오름차순, 혹은 내림차순으로 정렬이 되어 있을 때 시간초과가 날 거 같네요..
피벗 선택하는 방법 중에 중위법이라고 하는 게 있습니다.
간단하게 말하면
가장 좌측에 있는 것. 우측에 있는 것, 중간에 있는 것을 고른 다음에..
이 셋을 비교해서 중간값을 가지는 것을 피벗값으로 택한다. 이런 건데요..
한 번 검색해 보시는 것도 괜찮으실 거 같네요.
9248번 - Suffix Array
답은 도출되었다. 알고리즘은 맞으시다는 거네요.
그렇지만 시간 초과가 났다.
오름차순, 혹은 내림차순으로 정렬이 되어 있을 때 시간초과가 날 거 같네요..
피벗 선택하는 방법 중에 중위법이라고 하는 게 있습니다.
간단하게 말하면
가장 좌측에 있는 것. 우측에 있는 것, 중간에 있는 것을 고른 다음에..
이 셋을 비교해서 중간값을 가지는 것을 피벗값으로 택한다. 이런 건데요..
한 번 검색해 보시는 것도 괜찮으실 거 같네요.
??
알고리즘이 3값의 중위값을 피벗으로 택하는.
예를 들어서
가장 왼쪽에 있는 값이 0, 중앙에 있는 값이 9, 우측에 있는 값이 3이라면
중위값은 3이 나와야 합니다.
이쪽 한 번 참고해 보세요.
댓글을 작성하려면 로그인해야 합니다.
shfshfdl 6년 전 1
library를 쓰면 안되는 상황이라 qsort를 구현해서 입맛에 맞게 사용하고 싶은데
답은 도출되었지만 시간초과가 납니다.
아무래도 qsort의 조건이나 cmp 부분이 잘못된거 같은데..
아무리 봐도 이해가 되지 않아서 문의드립니다....
도움 부탁드리겠습니다.