[Baekjoon/C++] 1515번 - 수 이어 쓰기

[백준] Baekjoon Online Judge

문제로 이동

 

문제

세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다.

세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다.

세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다.

남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.)

 

입력

첫째 줄에 지우고 남은 수를 한 줄로 이어 붙인 수가 주어진다. 이 수는 최대 3,000자리다.

 

출력

가능한 N 중에 최솟값을 출력한다.

 

---

풀이

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;

    int num = 1;
    for (int i = 0; i < s.length(); ) {
        string n = to_string(num);

        for (int j = 0; j < n.length(); j++) {
            if (s[i] == n[j]) i++;
        }
        
        num++;
    }

    cout << num - 1 << '\n';

    return 0;
}

 브루트포스 알고리즘으로 1부터 N을 구할 때까지의 모든 숫자를 비교해서 답을 구했다. N의 최솟값을 구하기 위해서는 비교적 작은 숫자가 입력받은 배열에 포함되어 있어야 하기에 num을 1로 초기화하였다.

 예를 들어 입력으로 1111111이 주어진다면 1, 10, 11, 12, 13, 14가 남아있는 숫자로 체크되어야 최솟값을 구할 수 있다. 이런 11과 같은 숫자가 체크되기 위해서는 모든 자릿수의 숫자들을 s의 숫자와 비교해야 한다. 이때 21을 입력 받은 경우 이 숫자가 12로 인식될 수 있기에 무조건 자릿수가 높은 숫자부터 s와 비교해야 한다. 이를 편하게 구현하기 위해 <string>의 to_string()을 사용하여 num을 string으로 바꿔서 사용했다.