https://programmers.co.kr/learn/courses/30/lessons/42748
-
solution
단순 정렬 문제?
정렬에서 O(NlogN) 이 걸리기 때문에 이 부분을 줄이지 않는 이상 전체 시간복잡도는 줄지 않는다.
정렬값을 반환하는 것이 아닌 k번째 수를 반환하는 문제이기 때문에 이것저것 해보고 싶긴 하다.
min(k,n) (n==|i-j|) 길이의 배열만 정렬 유지? dynamic programming ?
다 n size만 줄고, 시간복잡도가 줄어드는 극적인 생각은 나지 않아 그냥 단순하게 풀기로 했다..
sort는 quick sort 이용 -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/A3.py
https://github.com/songjy6565/alg-js/blob/master/programmers/A3.js
https://github.com/songjy6565/alg-cpp/blob/master/programmers/A3.cpp -
P.S
다음부턴 cpp 은 작성하지 않도록 하겠다. 속도 좀 올리고 문제 난이도도 좀 올리고 해야 될 것 같다..
