백준 1038번, 감소하는 수

백준 1038번 c언어 문제풀이

문제:

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

풀이:

처음 이 문제를 보고 접근 방식을 일일이 숫자를 증가시키며 앞자리 수와 뒷자리수를 비교하는 식으로 문제를 풀었다.
하지만, 그렇게 문제를 풀었을 때 결과값은 맞게 나오지만 입력값을 높일 수록 시간이 오래걸리는 문제가 있었다.
제출했을 때에도 시간초과가 나왔다..

#include <iostream>
#include <cstdio>
#include <math.h>

using namespace std;

int main(){

int input; //입력값
int result; //결과값
int incre = 0; //감소하는 수가 맞다면 증가
int arr[100]; //구하려는 숫자의 각자리수 저장

cin >> input;

if(input==0){  // 0일때는 0출력
    cout << 0 ;
    return 0;
}
else if(input > 1023 ){
    cout << -1;
    return 0;
}

result = 0; // 1부터 증가시킨다.
while(incre < input){ // incre가 input과 같아질때까지 반복문
    result++;
    int count = 0; //자리수
    int cnt = result;

    while(cnt != 0){ //자리수 분리하기
    arr[count] = cnt % 10;  //낮은 자리부터 arr[]에 저장.
    cnt = cnt/10;
    count++;  //자리수 증가
    }

    for(int i=0;i<count;i++){  //자리수 비교하기, 비교해서 감소하는 수이면 incre 증가
    if( i == count-1 ){    
        incre++;
    }
    else if(arr[i] < arr[i+1]){
        continue;
    }
    else{
        break;
    }
    }
}
cout << result;
return 0;
}

위의 코드가 시간 초과가 난 코드이다..
사실 위의 코드를 작성할 때에도 어떤 숫자가 마지막 감소하는 숫자인지 고려하지 못하였다.
다른 방법이 떠오르지 않아 다른 분들의 코드를 보았다. 위의 코드가 얼마나 비효율적인 코드인지 알수 있었다.

다시 한번 풀어보자

먼저 내가 고를 수 있는 숫자는 0 ~ 9 까지이고 중복해서 고를 수 없다는 걸 알 수 있다.
그리고 만들 수 있는 수는:
0,1,2,..,10,20,21,..,320,321,430,431,..,9876543210이다.
구할수 있는 감소하는 수의 갯수를 조합식으로 보면:
10C1 + 10C2 + 10C3 + … +10C10이다.
총 2^10-1 = 1023이란걸 알수 있다.
자료형을 조심하도록 한다. long long 타입을 쓴다
일단 모든 조합을 다 구하고 큐에 저장해서 출력하는 방법으로 해보도록 하겠다.

1. 큐(q)에 1부터 9까지 저장한다. 다른 큐(q1)에도 1부터 9까지 저장한다.
2. q의 처음값을 다른 변수에 저장한다.
3. q를 pop해서 처음값을 없애준다.
4. 위의 저장한 값을 10으로 나눈 나머지보다 작은 수를 처음값에 10을 곱하고 더해준다. 이 수들을 q에 푸쉬해준다. ex. 처음 값이 3이었다면 q에서 3은 사라지고 30,31,32 가 생긴다.
5. 위의 값들을 q1에도 푸쉬한다. q1에는 감소되는 모든 숫자들이 저장된다.
6. q 안에 아무것도 남지 않을 때까지 반복문을 돌려준다.
7. q1에 모든 값들이 저장되있다. 반복문을 통해 구하려고 하는 값을 빼준다.

코드:

#include <iostream>
#include <math.h>
#include <queue> 
#include <vector>

using namespace std;

int main(){
    int input;
    queue <long long> q;
    queue <long long> q1;

    for(int i=0; i<=9; i++){
        q.push(i);    //0~9까지 queue 넣기 현재 큐[9,8,7,6,5,4,3,2,1,0]
        q1.push(i); //0~9까지 새로운 큐에 푸시
    }

    while(!q.empty()){//q가 비워질때까지 반복, 
        long long qnum = q.front(); // 첫 칸에 들어간수 qnum에 저장
        int el;

        el = qnum % 10; //나머지보다 작은수 이어붙이기 위해 나머지를 구한다.
    
        q.pop(); //queue 첫번째칸에 있는 수 빼낸다.
        for(int i=0; i<el; i++){
        long long num;
        num = 10*qnum + i;
        q.push(num); // queue에 새로만든수 push
        q1.push(num); //큐에 저장
        }
    }
    cin >> input;
    if(input >= q1.size()){
        cout << -1;
        return 0;
    }else{
        for(int i=0;i<input;i++){
        q1.pop();
        }
    }
    cout << q1.front();
    

    
    return 0;
}

https://gamedoridori.tistory.com/51

위의 블로그를 참고해서 만들었다.

이런 접근법을 스스로 생각해서 풀 수 있는 실력이 되면 좋겠다.