[C++] 백준 1427 소트인사이드

www.acmicpc.net/problem/1427

1427번: 소트인사이드

 

1. 서론

 

나에게 엄청 추억인 문제다... 막 3학년이 돼서 C밖에 모를 때 계속 풀다가 결국 포기했었던... 그렇게 어려운 문제는 아닌데 C로 풀려니까 벅찼던 듯^^,,

 

2. 문제 풀이

 

자연수가 주어지고 이 자연수를 자릿수 별로 분리해서 내림차순으로 정렬하는 문제이다.

 

문제가 간결하다 보니 풀이 방법도 각양각색인데 내가 제일 먼저 생각한 방법은 정말 단순하게 자연수를 자리수별로 분리해서 배열을 만들고 정렬하는 방법이다. 이게 제일 생각하기 쉬운 방법인 것 같다. 

 

그런데 정말 신기하게 푸는 방법을 발견했다.

배열을 0~9까지 만들고 자연수를 자리수별로 분리할 때 나오는 숫자를 배열로 카운트해준다.

그리고 내림차순으로 출력하기 위해 9부터 0까지 역순으로 배열의 값이 1이면 한 번 n번이면 n번 출력해준다.

예를 들어 98917이라면 

 

0 1 2 3 4 5 6 7 8 9

0 1 0 0 0 0 0 1 1 2

 

=> 배열에 이런 식으로 값이 들어가게 된다. 그리고 그 값을 

 

99 | 8 | 7 | 1

 

이런식으로 출력하는 것이다. 아이디어가 되게 신기했다. 

 

3. 코드 설명

 

1) 첫 번째 방법

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int main()
{
    string s;
    vector<int> v;
    int i, size;

    cin >> s;

    size = s.length();

    for (i = 0; i < size; i++)
        v.push_back(s[i] - 48);

    sort(v.rbegin(), v.rend());

    for (i = 0; i < size; i++)
        printf("%d", v[i]);   
}

 

숫자를 문자열로 받고 그 문자를 정수로 처리해서(아스키코드 이용) 배열에 넣어주고 역순으로 정렬한 후 출력한다.

 

2) 두 번째 방법

 

#include <iostream>

using namespace std;

int main()
{
    int n, i, j;
    int a[10];

    cin >> n;

    for (i = 0 ; i < 10; i++)
        a[i] = 0;

    while(n != 0)
    {
        a[n % 10]++;
        n /= 10;
    }
    
    for (i = 9; i >= 0; i--)
        for (j = 0; j < a[i]; j++)
            if (a[i] != 0)
                cout << i;   
}

 

숫자를 받고 10씩 나누면서 자릿수를 분리해 배열에 저장한다. 이때 배열에 각 index가 동일한 배열에 값을 0에서 1씩 카운트하는 방식으로 저장한다.

그리고 배열을 역순으로 보면서 그 배열의 값만큼 해당 숫자를 출력한다. 

이런 방법을 쓰면 따로 정렬할 필요가 없기 때문에 간결한 것 같다.