반응형
https://www.acmicpc.net/problem/1015
1015번: 수열 정렬
P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주
www.acmicpc.net
특정 수열을 오름차순으로 만드는 또 다른 수열을 구하는 문제이다.
가장 쉽게 생각할 수 있는 방법은 현재 수열에서 가장 작은 숫자를
순차적으로 뽑아내어 해당 인덱스를 배열로 만들면 풀 수 있다.
단, 쉬운만큼 시간은 O(n^2)가 걸리므로 조금 더 어려운 조건일 경우
시간을 줄이는 방법을 새로 생각해야한다.
#define MAXIMUM 1001
int N;
int A[51];
int B[51];
int get()
{
int smallist = 0;
for (int i = 0; i < N;i ++)
if (A[smallist] > A[i])
smallist = i;
A[smallist] = MAXIMUM;
return smallist;
}
int main()
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
scanf("%d", &A[i]);
for (int i = 0; i < N; i++)
B[get()] = i;
for (int i = 0; i < N; i++)
printf("%d%c", B[i], (i == N - 1) ? '\n' : ' ');
return 0;
}
반응형