본문 바로가기

Programming Problems/Arrays

주어진 배열 패턴대로 배열 정렬하기

패턴은 1 ... N 의 값의 조합 배열으로 주어진다.

배열은 서로 다른 N개의 값이다.

패턴대로 배열을 정렬해 보자.


O(N^2), O(1) 은 partition 해가면서 각 K번째 원소를 찾으면 가능하다.


근데 O(NlogN) O(1) 알고리즘이 있대..


조합 배열을 정렬한 후에 패턴 배열에 원하는 값을 입히고 패턴 배열을 출력한다.. 추가 공간은 안 쓰는 듯?


더 좋은 O(N) O(1) 알고리즘이 있대..


public static int[] sort2(int[] Xs, int[] As) {
        for (int i = 0; i < Xs.length; i++) {
            while(As[i] != i) {

                int a = As[i];

                // swap Xs
                int x = Xs[a];
                Xs[a] = Xs[i];
                Xs[i] = x;

                // swap As
                As[i] = As[a];
                As[a] = a;
            }
        }

        return Xs;
    }


알고리즘 요점은..


16 3 17 11 5 8

2  3  1   0  4 5


를 A에 맞춰서 정렬하면(counting sort와 같게 O(N) 이다)

11 17163  5  

0  1  2  3  4  5


안되는데 ..??


첫 행렬이 정렬되어 있다는 가정 아래 하는듯


아 내꺼가 그럼 훨신 간단하잖아 ............

뭐하는거야 이게 이상한 풀이 가지고 장난치네;;


https://www.careercup.com/question?id=4669539153346560