3004 : 데이터 재정렬

문제 설명

프로그래밍 문제를 풀다 보면 뒤죽박죽인 N개의 데이터를 숫자의 크기 순으로 0 ~ N-1까지의 숫자로 재정렬 해야되는 경우가 종종 있다.

예를 들어 N=5 이고,

50 23 54 24 123

이라는 데이터가 있다면,

2 0 3 1 4

가 된다.

데이터를 재정렬하는 프로그램을 작성하시오.

 

입력

첫째 줄에 데이터의 개수 N이 입력된다. ( 1 <= N <= 50,000)

둘째 줄에 공백으로 분리되어 N개의 서로 다른 데이터가 입력된다. (값의 범위:0~500,000)

 

출력

N개의 데이터를 0 ~ N-1로 재정렬하여 출력하라

 

 

입력 예시                                                                             출력 예시

5                                                                                           2 0 3 1 4

50 23 54 24 123

 

 

 

 

 

1차 시도

 

#include <stdio.h>

int main()
{
    int n, a[50000],b[50000],i,j,tmp; 
    scanf("%d",&n);
    for(i=0; i<n; i++){
        scanf("%d",&a[i]);
        b[i] = a[i];
    }
    for(i=0; i<n; i++){
        for(j=i; j<n; j++){
            if(a[i] > a[j]){
                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
    }
    for(i=0; i<n;i++){
        for(j=0; j<n; j++){
            if(b[i] == a[j])
                printf("%d ",j);
        }
    }
}

 

a[i]로 받고 b[i] = a[i] 시켜둔 뒤 오름차순으로 정렬시키고 밑에 이중포문으로 원래 배열이 담긴 b[i] 값이 오름차순으로 정렬된 a[j] 값과 같으면 j 값을 출력하게 했는데 시간초과 뜸... 😢 밑에 다른 시간초과 오류난 거 보니까 이중 포문으로 짜면 안 되구... sort 문제이니 퀵솔트나 머 그런 거 써야 한다구 함

🔽 그렇다고 한다...!

 

 

 

2차 시도

 

#include <stdio.h>
#include <stdlib.h>
void quicksort(int* arr, int left, int right)//퀵정렬
{
    int L = left, R = right;
    int temp;
    int pivot = arr[(L + R) / 2];

    while (L <= R)
    {
        while (arr[L] < pivot) L++;
        while (arr[R] > pivot) R--;
        if (L <= R)
        {
            if (L != R)
            {
                temp = arr[L];
                arr[L] = arr[R];
                arr[R] = temp;
            }
            L++;
            R--;
        }
    }
    if (left < R) quicksort(arr, left, R);
    if (right > L) quicksort(arr, L, right);
}

int main()
{
    int n, *a,b[50000],i,j,tmp; 
    scanf("%d",&n);
    a = (int*)malloc(sizeof(int) * n);
    for(i=0; i<n; i++){
        scanf("%d",&a[i]);
        b[i] = a[i];
    }
    quicksort(a, 0, n - 1);
    for(i=0; i<n;i++){
        for(j=0; j<n; j++){
            if(b[i] == a[j])
                printf("%d ",j);
        }
    }
    free(a);
}

이것도 시간초과 뜨넹... 퀵 정렬로 풀었는데 왜 안 되는 지 모르겠다. 지대짱나 ㅠ;;

다른 분 티스토리 보니까 print 부분도 함수 써 갖고 한 듯

 

 

 

 

3차 시도

 

#include <stdio.h>
#include <stdlib.h>

void quicksort(int* arr, int left, int right)//퀵정렬
{
    int L = left, R = right;
    int temp;
    int pivot = arr[(L + R) / 2];

    while (L <= R)
    {
        while (arr[L] < pivot) L++;
        while (arr[R] > pivot) R--;
        if (L <= R)
        {
            if (L != R)
            {
                temp = arr[L];
                arr[L] = arr[R];
                arr[R] = temp;
            }
            L++;
            R--;
        }
    }
    if (left < R) quicksort(arr, left, R);
    if (right > L) quicksort(arr, L, right);
}

void printNum(int* arr, int L, int R, int* num)
{
    int m = (L + R) / 2;
    if (L <= R)
    {
        if (*num > arr[m]) printNum(arr, m + 1, R, num);//오름차순배열 중앙값보다 클때
        else if (*num < arr[m]) printNum(arr, L, m - 1, num);//오름차순배열 중앙값보다 작을때
        else *num = m;//중앙값과 num( temp[i] )이 같을때
        //오름차순 arr배열의 자리 num( <- temp[i] ) 에 저장
    }
}

int main()
{
    int* data, * temp;
    int n, i, m;

    scanf("%d", &n);

    data = (int*)malloc(sizeof(int) * n);
    temp = (int*)malloc(sizeof(int) * n);

    for (i = 0; i < n; i++)
    {
        scanf("%d", &m);
        data[i] = m;
        temp[i] = m;
    }

    quicksort(data, 0, n - 1);//퀵정렬

    for (i = 0; i < n; i++)
    {
        printNum(data, 0, n - 1, &temp[i]);//temp[i]의 자리를 오름차순배열 data에서 찾아 temp[i]에 대입
        printf("%d ", temp[i]);
    }

    free(data);
    free(temp);

    return 0;
}

구글을 살짝쿵 참고했당 ㅎㅎ;

2번째 코드와의 차이점은 원래 코드에서 b[i]로 취급되던 걸 포인터로 써서 동적할당을 해줬고, print 할 때도 정렬을 사용해줬당