[C++][백준 9047번] Kaprekar 6174 문제

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

9047번: 6174

 

1. algorithm 헤더파일 사용

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int N;
int cnt = 0;

void InputData(){
	cin >> N;
}

string findsub(string Nstr){
    sort(Nstr.begin(), Nstr.end());
    int min = stoi(Nstr);
    reverse(Nstr.begin(), Nstr.end());
    int max = stoi(Nstr);

    cnt++;
    return to_string(max - min);
}

int main(){
	InputData();
    string Nstring = to_string(N);

    while (Nstring != "6174")
    {
        Nstring = findsub(Nstring);
    }
	cout << cnt << endl;
	return 0;
}

• algorithm 헤더파일 사용 (퀵 정렬)
• string 사용

algorithm 헤더파일에 있는 sort 알고리즘을 사용해서 푼 예시이다.

해당 sort 알고리즘은 퀵 정렬을 기반으로 구현되어 있다.

시간 복잡도: nlogn

2008 입력에 대해 6 출력

 

 

2. 버블 sort 사용

#include <iostream>
using namespace std;

int N;
int cnt = 0;

void InputData(){
	cin >> N;
}

int sortfindsub(int* d){
    int asc_num;
    int dec_num;
    for (int i=3; i>=1; i--){
        for(int j=0; j<i; j++){
            if(d[j] > d[j+1]){
                int tmp = d[j+1];
                d[j+1] = d[j];
                d[j] = tmp;
            }
        }
    }

    asc_num = d[0]*1000 + d[1]*100 + d[2]*10+d[3]*1;
    dec_num = d[0]*1 + d[1]*10 + d[2]*100+d[3]*1000;
    return dec_num-asc_num;
}

int kaprekar(int N){
    int d[4];
    for(int i=0; i<4;i++){
        d[i] = N%10;
        N = N/10;
    }
    cnt++;
    return sortfindsub(d);
}

int main(){
	InputData();

    while (N != 6174)
    {
        N = kaprekar(N);
    }
	cout << cnt << endl;
	return 0;
}

 

• int (배열) 만 사용
• bubble sort : 시간복잡도 O(n^2)
• pointer

으로도 구현해 보았다.

bubble sort 개념을 이해하고 혼자 구현했을 때는 i-- j++ 중첩으로 했는데, 찾아보니 i++ j++ 중첩으로 많이 구현하는 듯 하다.!