[C] 코드업 문제풀이 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

50 23 54 24 123

 

 

 

출력 예시

2 0 3 1 4

 

 

도움말

50 23 54 24 123 에서

23, 24, 50, 54, 123 순서로 0, 1, 2, 3, 4 가 된다.

그리고 원래의 위치대로 출력한다.

---

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

int main(void){
    int n,count=0;
    scanf("%d", &n);
    int *arr1=(int*)malloc(n*sizeof(int));
    int *arr2=(int*)malloc(500000*sizeof(int));

    for(int i=0;i<n;i++){
        scanf("%d", &arr1[i]);
        ++arr2[arr1[i]];
    }
    for(int i=0;i<500000;++i){
        if(arr2[i]>0){
            arr2[i]=count++;
        }
    }
    for(int i=0;i<n;i++){
        printf("%d ",arr2[arr1[i]]);
    }
    free(arr1);
    free(arr2);

    return 0;
}

이 문제는 코드를 결국 가져와서 하나 하나 분석해보도록 하겠다.

 

처음에 나는 이 문제를 보았을 때 배열로 풀수 있을 것이라고 생각했다. 하지만 잘 되지 않았다. 무언가가 꼬였다. 순서를 바꾸긴 하더라도 이것을 다시 원래 대로 어떻게 확인하고 출력을 할것인지가 문제였다. 그래서 한번 어떻게 하는지 보았는데 내가 본 코드는 메모리 할당이었다. 배열을 가지고 오긴 하지만 메모리할당을 통해서 만드는 것이었다. 메모리 할당, 이제 개념과 어떻게 해야하는지는 감이 오는데 언제 써야 하는지 잘 모르겠다.

 

코드를 뜯어보자면

일단 몇번 반복할 것인지 저장해주는 것은 크게 다르지 않다.

그리고 이제 메모리 할당을 위한 작업이 필요하다.

포인터를 이용하는 것은 메모리 할당을 알게 되면 이해가 된다.

일단 arr1은 자리 숫자를 위한 작업이고 arr2는 아무래도 값의 범위를 나타내는 것이라고 할 수 있을 것이다. 모두 숫자이므로 int형 만큼 자리 확보가 필요하다. 그 다음에 for문을 이용하는데 arr1에 값을 각각 저장하는 것은 쉽게 알 수 있다. 그 다음에 arr2에 그 숫자로 위치를 넣어준다. 

다음 for문을 해보도록 하겠다. 이제는 전체 범위에서 봐주는 작업이 필요하다. 값이 넣어진 자리는 0보다 클 것이므로 여기에 count를 해준다. 이게 왜 등장하는지 의문이 처음엔 들기도 했는데 이 원리는 다음과 같다.

이제 처음 변수가 선언되었을 때에는 0이다. 그리고 이제 첫번째로 i자리에서는 count가 1번 되어서 더해지게 된다. count는 계속 초기화가 아니라 계속 누적이 되게 된다. 다음 숫자를 만났을 때에는 2가 되고 그 다음 숫자를 만나면 3 이렇게 누적이 되게 된다. 

마지막 for문에서는 최종 출력 과정이다. 저장 방식과 마찬가지로 출력을 해야 한다. 이것을 이해하는데에는 어려움이 크게 되지 않는다. 자릿수가 있기 때문이다.

마지막에 메모리 할당 해제를 해주고 반환하면 끝이다.