엘리스 코드 챌린지 Day 7 계기판 조작하기

문제

 

풀이

처음 이 문제를 봤을때 손도 못댔었는데 정답 코드를 보니 조금 허무했습니다.

이런게 애드혹이겠죠.. ㅠ

 

우선 N의 범위가 10^7이기 때문에 범위 내에서는 8종류의 수까지 표현할 수 있습니다.

따라서 K가 9, 10인 경우에는 9, 10종류의 수를 사용한 가장 작은수를 출력하면 그게 답입니다.

K = 9일 때는102345678이 되겠고, K = 10일 때는 1023456789가 되겠습니다.

 

그러면 나머지의 경우는 많아봐야 1천만 정도라서 N을 1씩 증가시키면서 직접 비교해도 시간 안에 문제를 해결할 수 있습니다.

저는 N + 1을 문자열로 만들어서 각 자리를 카운팅한 다음 카운팅한 갯수가 정확이 K개인지 확인하는 방식으로 구현했습니다.

N + 1을 계속 하기때문에 무조건 N보다는 큰 숫자일 수밖에 없고, 그 수가 정확이 K개의 숫자만 사용했다면 그게 정답이 됩니다.

 

코드

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
 
string str;
int K;
bool chk[10];
 
void func() {
    if (K == 10) {
        cout << "1023456789\n";
        return;
    }
    if (K == 9) {
        cout << "102345678\n";
        return;
    }
 
    while (1) {
        str = to_string(stoi(str) + 1);
        int cnt = 0;
        for (auto x : str) {
            if (chk[x - '0']) continue;
            cnt++;
            chk[x - '0'] = true;
        }
 
        if (cnt == K) {
            cout << str << '\n';
            return;
        }
 
        memset(chk, false, sizeof(chk));
    }
}
 
void input() {
    cin >> str >> K;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}