[1015번] 수열 정렬

문제 출처 :

https://www.acmicpc.net/problem/1015

알고리즘 분석 :

문제 해결에 필요한 사항

1. 정렬

문제 이해가 처음에는 조금 어려울 지 모르나 직접 수를 넣어보며 문제를 생각해본다면 이해 할 수 있다.

예제 입력에 없는 내용으로 한번 생각해보자.

5
600 200 300 400 500

일때 어떻게 될까?

답은 4 0 1 2 3 이다.

왜 이렇게 나오는지 답을 한번 구해보자.

B[P[i]] = A[i] 라는 식을 이용하여 아래처럼 표현 할 수 있다.

B[] = 600

B[] = 200

B[] = 300

B[] = 400

B[] = 500

이때 B에 index를 부여해보자.

B[0] = 600

B[1] = 200

B[2] = 300

B[3] = 400

B[4] = 500

이후 B의 값을 기준으로 정렬을 한번 해 보자.

B[1] = 200

B[2] = 300

B[3] = 400

B[4] = 500

B[0] = 600

이 값에 대해 정답이 되는 index를 한번 더 부여해보자.

B[1,0] = 200

B[2,1] = 300

B[3,2] = 400

B[4,3] = 500

B[0,4] = 600

이제 마지막으로 다시 원래대로 돌아가기 위해 B의 첫번째 값을 기준으로 정렬해보자.

B[0,4] = 600

B[1,0] = 200

B[2,1] = 300

B[3,2] = 400

B[4,3] = 500

이렇게 한다면 두번째 값에 정답이 나와있음을 알 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
typedef struct _INFO_
{
    int idx;
    int ans;
    int val;
}INFO;
 
INFO info[1002];
 
bool compVal(const INFO &a, const INFO &b)
{
    if(a.val != b.val) // 사전 순 정렬
        return a.val < b.val;
    return a.idx < b.idx;
}
 
bool compIdx(const INFO &a, const INFO &b)
{
    return a.idx < b.idx;
}
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &info[i].val);
        info[i].idx = i;
    }
 
    sort(info, info + n, compVal);
 
    for (int i = 0; i < n; i++)
        info[i].ans = i;
 
    sort(info, info + n, compIdx);
 
    for (int i = 0; i < n; i++)
        printf("%d ", info[i].ans);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>