[BOJ] 1015번. 수열 정렬

문제 링크 : https://www.acmicpc.net/problem/1015

문제는 링크 참고.

풀이.

문제에 나와 있듯이 "B[P[i]] = A[i]" 식을 이용해서 풀면된다.

입력예제 "2 3 1" 에서 출력예제 "1 2 0" 이 나오는 이유는

A { 2 3 1 }

P { 1 2 0 }        이 있다면

B[P[0]] = A[0] = B[1] = 2

B[P[1]] = A[1] = B[2] = 3

B[P[2]] = A[2] = B[0] = 1

결과적으로 B { 2 3 1 }이 완성되고, B는 A로부터 정렬된 수열이란 것을 알 수 있다.

#include <stdio.h>
#include <algorithm>
#define MAX 51
 
using namespace std;
 
class Data {
    public:
        int index;
        int value;        
}arr[MAX];
 
bool Comp(const Data left, const Data right) {
    if (left.value != right.value)
        return left.value < right.value;    
    else
        return left.index < right.index;
}
 
int ans[MAX];
 
int main() {
    int N = 0;
    
    scanf("%d", &N);
    
    for (int i = 0 ; i < N ; i ++) {
        arr[i].index = i;
        scanf("%d", &arr[i].value);    
    }
    
    sort(arr, arr + N, Comp);
    
    for (int i = 0 ; i < N ; i ++)
        ans[arr[i].index] = i;
        
    for (int i = 0 ; i < N ; i ++)
        printf("%d ", ans[i]);
    
    return 0;
}

위 방법보다 더 쉬운 방법도 있다.

숫자를 입력받을 때 각 숫자에 카운팅을 매겨, 순위를 구해서 답을 구한다.

다른 사람 소스보고 알았다 ㅋㅋ

왜 이런 방법을 생각을 못 했을까..

#include<stdio.h>
 
const int MAX_N = 50;
 
int n, a[MAX_N], b[MAX_N];
 
int main(){
    scanf("%d",&n);
 
    for(int i = 0; i < n; i ++){
        scanf("%d",a+i);
 
        for(int j = 0; j < i; j ++)
            a[j] > a[i] ? b[j] ++ : b[i] ++;
    }
 
    for(int i = 0; i < n; i ++)
        printf("%d ", b[i]);
 
    return 0;
}