1377번 - 버블 소트
소팅전 배열과 퀵소트를 한 후 배열을 가지고 어떻게 요리하는것같은데 ..,아닌가요 ?ㅠㅠ
잘모르겠네여 ㅠㅠ 힌트좀주시면안될까요 고수님들..
버블소트로 원래 위치까지 가려면
원래 위치가 더 뒤쪽이면 한 번만에 갈 수 있지만
원래 위치가 더 앞쪽이면 떨어진 거리만큼을 반복해야 하죠
저는 qsort와 bsearch를 이용하여 해결했습니다
저는 어떤 수 하나의 스왑 횟수는 자기 앞에 있는 자기보다 큰 수들의 갯수만큼이라는 점을 이용해
이 갯수를 모든 수에 대해 인덱스 트리로 세고 그 중 가장 큰 값을 뽑았습니다.
저는 '어떤 원소보다 작은 원소 개수(혹은 큰 원소 수)' 를 알수 있는 RB트리를 새로 짜서
현재 배열을 차례대로 rb트리에 넣으면서 넣기전에 그것보다 큰 원소 수를 셌습니다.
댓글을 작성하려면 로그인해야 합니다.
kdhsong 9년 전
소팅전 배열과 퀵소트를 한 후 배열을 가지고 어떻게 요리하는것같은데 ..,아닌가요 ?ㅠㅠ
잘모르겠네여 ㅠㅠ 힌트좀주시면안될까요 고수님들..