문제

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

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

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

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

입력

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

출력

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

예제 입력

234092

예제 출력

20

내가 했던 풀이 방법

1. current를 1, index를 0으로 초기화해준다. current는 현재 검사하고 있는 수이며, 1부터 1씩 증가해나간다. index는 입력받은 수를 각 자릿수들을 배열로 number에 저장해주게 되는데 이 number의 index를 관리해준다.
2. index가 num.length가 되기 전까지 아래 연산을 반복한다.
3. 현재 current를 문자열로 바꿔준 뒤, ""을 기준으로 분할한 배열을 number에 저장해준다.
4. 0부터 number.length까지 순회하면서 number[i]가 입력받은 수의 자릿수 중 하나일 때, index를 1 증가시켜준다. 이때, index가 num.length가 되면 for문을 중단한다.
5. for문이 끝날 때마다, current를 1씩 증가시켜준다.
6. for문을 탈출하고, current가 1증가 된 뒤에 while문을 탈출하기 때문에 결과로 출력하는 current는 -1을 한 값을 출력해주어야 한다.

문제가 다소 복잡하므로 예제 입력을 기준으로 상황을 설명한다.

1. 입력받은 수가 234092일 때, current는 1이므로 number은 [1]이고, num은 [2, 3, 4, 0, 9, 2]이다. number[0]과 num[index]는 다르므로, 아무것도 하지 않고 for문이 끝난다. for문이 끝난 뒤, current가 1 증가하여, current는 2가된다.
2. current가 2이므로 number은 [2]이다. number[0]과 num[index]가 2로 같으므로, index를 1 증가시킨 뒤, for문을 끝낸다. current는 3이 된다.
3. current 3과 current 4는 2번과 같은 방식으로 진행된다. current 4까지 진행한 뒤, current는 5가 되고 index는 3이 된다.
4. current 5부터 current 9까지 1번과 같은 방식으로 진행된다. current 9까지 진행한 뒤, current는 10이 되고 index는 여전히 3이다.
5. current 10은 number이 [1, 0]이므로, number[1]과 num[index]가 0으로 같으므로, index를 1 증가시킨 뒤, for문을 끝낸다. current는 11이 된다.
6. current 11부터 current 18까지 1번과 같은 방식으로 진행된다. current 18까지 진행한 뒤, current는 19가 되고, index는 4이다.
7. current 19는 number이 [1, 9]이고, number[1]과 num[index]가 9로 같으므로, index를 1 증가시킨 뒤, for문을 끝낸다. current는 20이 된다.
8. current 20은 number이 [2, 0]이고, number[0]과 num[index]가 2로 같으므로, index를 1 증가시킨 뒤, for문을 끝낸다. current는 21이 된다.
9. index가 num.length와 같아졌으므로 반복문을 탈출한다. current-1을 출력하므로 최솟값은 20이 된다.

코드

var fs = require('fs');
let num = fs.readFileSync(0, 'utf-8').toString().trim();

let current = 1;
let index = 0;
while (true) {
  if (index >= num.length) break;
  number = current.toString().split('');
  for (let i = 0; i < number.length; i++) {
    if (number[i] === num.charAt(index)) {
      index++;
      if (index >= num.length) break;
    }
  }
  current++;
}

console.log(current - 1);

회고

문제가 생각보다 복잡한 게 많은데, 그렇다고 복잡하게 풀면 코드가 꼬여버리는 문제가 발생한다... 처음에 문제를 보고 생각한 첫 풀이는 이전 수가 23이고, 현재 수가 4일 때 20+4 또는 4×10 또는 23+1 ... 이런식으로 나올테니 그런 수들 중에 제일 작은 값을 사용하자! 이런식으로 코드를 짯는데 다음에 나오는 수가 현재 수에 포함될 수도 있다는 점에서 바로........ 포기를 선언했다. 예를 들어 현재가 1이고, 다음 수가 1일 때 11이 모두 지워지지 않았을 수도 있고, 101인데 0이 지워졌을 수도 있고? 경우의 수가 너무 많았던 것이었다. 그래서 정말 브루트포스 알고리즘 풀이 방식대로 풀어보자. 하다가 생각해낸 풀이인데 current 증가식을 for문 안에 넣어서 헛발질을 좀 많이 했지만, 그래도 복잡했던 것치고는 빠르게 풀이했던 것 같다.