[1427번] 소트인사이드

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 정렬

2. 정렬을 생각하는 여러가지 방법

N은 1,000,000,000보다 작거나 같다 라고 적혀있다. 이말은 즉, 배열에 모든 값을 넣어 정렬은 

메모리 오버플로우를 초래하기에 진행 할 수 없는 방식이다.

그렇다면 다른 방식을 생각 해 보아야 하는데 여러가지 방법 중 한가지는 문자열로 생각해 보는 방식이다.

예를들어 1이라는 문자를 받으면 1은 49번 아스키 코드이기에 b['1'-48] == b[1]이다. 따라서 b[1]++;를 해준다면

1이라는 값이 하나 증가했다는 의미로 해석 할 수 있다.

그렇게 1123345를 입력하면

b[1] = 2, b[2] = 1, b[3] = 2, b[4] = 1, b[5] = 1가 될것이고, b[9] 배열부터 b[0] 배열까지 거꾸로 1씩 빼며 출력을 하면

5 4 3 3 2 1 1이 출력된다.  

소스 코드 : 

#include <stdio.h>
#include <string.h>
 
int main()
{
    char a[15];
    int b[15] = {0,};
    int i,len;
    
    // 처음에는 문자열로 값을 받는다.
    scanf("%s",a);
    
    len = strlen(a);
    
    // 문자열로 받은 값을 숫자로 변환시키되 
    // int배열에는 그 숫자에 해당하는 배열번호에 값을 1씩 증가시킨다.
    // ex :: 1123이면 b[1] = 2, b[2] = 1, b[3] = 1
    for(i = 0 ; i < len ; i ++)
        b[a[i]-48]++;    
     
    // b배열의 9번 배열번호에 있는 값부터 1씩 빼며 
    // 차례대로 출력하면 정렬되어 출력되는것과 같은 역할을 한다.
    for(i = 9 ; i >= 0 ; i --)
    {     
     while(b[i] != 0)
     {
      printf("%d",i);
      b[i]--;
     }     
    }
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>