걸음마부터 달리기

정렬방법을 따지는 문제는 아닌거같고 임의의 정렬이 나왔을때 어떻게 구현할건지에 대한 문제이다. 임의의 기준 정렬은 1) Comparator() {public int compare(T o1, T o2) {~}}를 통해 정렬기준을 오버라이딩 및 익명객체로 Arrays.sort에 전달 2) String의 사전식 정렬은 이미 Comparable의 compareTo 메서드에 구현이 되어있다.import java.util.*;import java.lang.*;import java.io.*;// The main method must be in a class named "Main".class Main { public static void main(String[] args) throws Exception { ..

5초인데 천만개를 받고 자리수가 10000보다 작으니까 2^100보단 무조건 작다. 따라서 O(nlogn)은 된다는건데... 그래서 Arrays.sort 하면 평균값 O(nlogn), 최악 O(n^2)이니까 이건 불확실하다. (O(n^2)을 저격하는 테케가 있으면 안되겠지...)그러면 안전하게 풀려면 O(n)과 유사하게 풀어야된다는거같은데...이러면 O(Kn)을 가지는 기수정렬을 써야한다. 큐에 넣어도 되지만 나는 그냥 bucket이라는 배열을 만들어놓고 각 끝자리에 맞게 index 맞춰서 넣었다.중요한게 bucket에 넣고 이 순서대로 다시 빼고,그 순서로 다시 bucket에 넣어서 다음 자리 기준으로 정렬한다.이걸 최대 자리 수만큼 반복하면 된다. 문제는 이 과정에서 "합배열" 을 사용한다. 어떠한 ..