백준 1515번 수 이어 쓰기 - C++

문제

---

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

 

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

 

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

 

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

 

입력

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

 

출력

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

 

문제 링크

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

 

 

풀이

---

잘못된 접근

접근이 상당히 까다로웠다.

답은 웬만하면 가장 뒷자리의 수를 토대로 나오기 때문에 '뒷자리의 수를 하나씩 늘려가면서 수를 전부 써야하나?' 하는 생각을 해봤다.

허나 그렇게 하면 말도 안되게 많은 경우를 탐색하며, 문자열을 생성하고 제거하는 작업을 수행해야하기 때문에 이 방법은 말이 안된다고 결론 내렸다. ▼

말이 안되는 브루트 포스

 

 

올바른 접근

그러면 어떻게 접근을 해야하나 한참 고민하다가 결국 접근법을 봤다.

결론적으로 따지면 브루트 포스는 맞다.

그런데 문자열을 만들어서 확인하기 보다, 수를 순서대로 보면서 문자열에 있는 수를 제거하는 방식이었다.

 

`234092`라는 수가 있다고 할 때 1부터 하나씩 증가시켜가며 `234092`의 앞자리부터 동일한 수가 있으면 제거해나가면 된다는 것이다.

 

 

'그러면 동일하지 않은 수가 있으면 어떡해?'

 

 

동일하지 않은 수가 있으면 '지워진거지!' 하고 넘겨버릴 수 있다.

 

 

프로그램 동작

---

1부터 시작하여 주어진 문자열의 맨 앞자리부터 확인한다.

`234092`라는 문자열이 들어왔다고 하면, 1은 맨 앞자리 2와 같지 않기에 지워진 수라고 판단하고 넘어간다. ▼

 

1 다음은 2, 2와 `234092`의 가장 앞자리 수가 2로 같기에 `234092`의 2를 제거해준다. ▼

 

2 다음은 3으로 앞에서 한 것과 동일하게 수행해준다.

3과 `34092`의 가장 앞자리 수가 3으로 같기에 `34092`의 3을 제거해준다. ▼

 

 

이 과정을 4, 5, 6, ... 문자열이 전부 사라질 때 까지 수행해준다.

허나 지금까지는 한자리 수였기에 한번만 비교만 하면 됐는데, 10부터는 한번만 비교하는게 아니라 각 자리수를 다 비교해줘야한다.

 

9까지 비교를 하면 문자열은 `092`가 된다.

여기서 10과 비교를 하면 아래와 같이 각 자리수의 수를 모두 비교해줘야한다. ▼

 

 

위의 과정을 문자열이 모두 사라질 때 까지 수행하면 된다.

 

 

C++ 코드

---

#include <iostream>

using namespace std;

string N;
int NIdx, num = 1;

int main() {
    cin >> N;

    while (NIdx != N.length()) {
        string numString = to_string(num);

        for (int i = 0; i < numString.length(); i++) {
            if (N[NIdx] == numString[i]) {
                NIdx++;
                if (NIdx >= N.length()) {
                    cout << num;
                    exit(0);
                }
            }
        }
        num++;
    }
}

 

앞에서는 제거를 했다고 했는데, 필자는 정말로 제거를 하는 작업은 뺐다.

대신 `string N`의 인덱스를 기록하는 `NIdx`를 두었다.

결국에는 마지막 숫자까지 있는지 찾기만 하면 되는거고, 주어진 문자열이 바뀌거나 인덱스를 역주행하는 일 없이 쭉 진행하기 때문에 단순히 인덱스만 기록해도 별 지장없다.