백준 1015번 수열 정렬 :: 마이구미

이번 글은 백준 알고리즘 1015번 "수열 정렬" 을 다뤄본다.

문제 이름을 보다시피 정렬 관련 문제다.

P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.

배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

문제의 키워드는 비내림차순과 사전순으로 볼 수 있다.

문제를 해결하기 위해 수열 P를 구해보자.

적용하는 방법으로 나와있는 B[P[i]] = A[i]를 예로 표현해보자.

문제의 예제와 같이 N = 3, A = 2 3 1 주어졌을 경우를 보자.

위 그림을 보면 주어지는 A의 값들과 그에 대한 인덱스가 존재한다.

내림차순을 위해 값을 기준으로 정렬을 한다. (값에 대한 인덱스는 유지한다.)

for (int i = 0; i < n; i++) {
    int v = sc.nextInt();

    list.add(new Pair(i,v));

}

Collections.sort(list, ....);

위와 같이 값과 인덱스를 리스트 형태로 저장한 후 내림차순을 위해 정렬한다.

(sort 관련 오버라이딩은 아래에서 다루겠다)

정렬된 결과를 어떻게 활용하는지 보자.

for (int i = 0; i < n; i++) {
    p[list.get(i).idx] = i;
}

p[2] = 0;
p[0] = 1;
p[1] = 2;

정렬 후 변경된 사항을 확인할 수 있다.

정렬되면서 값에 대한 인덱스가 변경되었기 때문에 위와 같은 결과가 나온다.

B[0], B[1], B[2] 형태는 유지해야되기 때문에 P[2] = 0, P[0] = 1, P[1] = 2라는 결과를 알 수 있다.

정렬된 리스트의 인덱스를 활용하여 수열 P를 얻을 수 있게 되었다.

마지막으로 비내림차순과 사전순을 위한 sort 오버라이딩 부분을 보자.

Collections.sort(list, new Comparator<Pair>() {
    @Override
        public int compare(Pair o1, Pair o2) {
        // TODO Auto-generated method stub

        if (o1.value < o2.value) {
            return -1;
        } else if (o1.value > o2.value) {
            return 1;
        } else {
            if (o1.idx < o2.idx) {
                return -1;
            } else {
                return 1;
            }
        }
    }
});

값을 기준으로 정렬하면서 사전순 정렬을 위해 인덱스를 통해 한번 더 기준을 두었다.

값과 인덱스를 쌍으로 저장함으로써 쉽게 문제를 해결했다.

전체 소스는 Github URL을 통해 확인하길바란다.

백준 알고리즘 문제 1015번 "수열 정렬" 전체소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/sort/1015.java