문제 링크
1515번: 수 이어 쓰기
세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준
www.acmicpc.net
문제 설명
1부터 N까지 순서대로 써놓았는데 몇 개의 숫자가 지워진 상태다. 이 상태가 주어질 때 N의 최솟값을 구하는 문제이다. 아무것도 지워지지 않았을 수도 있다.
풀이 방법
주어지는 수의 최대 길이가 3,000자리 이고, 0~9까지 10개이기 때문에 30,000 이내에서 찾을 수 있다.
문제를 풀기 위해 두 가지 변수를 사용할 것이다. 하나는 입력 받은 문자에서 현재 보고 있는 index를 저장할 pointer변수, 다른 하나는 현재 값을 의미하는 answer이다.
문제에서 주어진 예시인 234092를 가지고 예를 들어보자. 현재 pointer=0, base=1인 상태다.
base와 현재 pointer가 가리키는 숫자는 같지 않기 때문에 base는 1을 더해주어 2가된다.
그러면 base와 pointer가 가리키는 숫자가 같아지기 때문에 pointer는 3을 가리키게 된다. 또한 base는 이미 일치하는 숫자를 찾았기 때문에 1을 더해 3이 된다.
base가 3일 때 pointer가 가리키는 숫자 3과 같기 때문에 이전 단계와 같이 pointer는 다음 숫자를 가리키게 되고, base는 1을 더해 4가 된다.
마찬가지로 base가 4일 때 pointer가 가리키는 숫자 4와 같기 때문에 이전 단계와 같이 pointer는 다음 숫자를 가리키게 되고, base는 1을 더해 5가 된다.
base는 5지만 pointer는 0을 가리키고 있기 때문에 base만 증가하게 된다. 하지만 증가해도 base와 pointer가 가리키는 숫자가 같지 않기 때문에 base=6, base=7, base=8, ..., base=10까지 증가한다.
base는 두 자리 숫자가 되었고, 십의 자리인 1과 pointer가 가리키는 숫자는 다르지만, 일의 자리 0과는 같기 때문에 base와 pointer가 같이 증가한다.
현재 base는 pointer가 가리키는 숫자와 십의 자리와 일의 자리가 모두 다르기 때문에 base만 증가하게 된다.
base=11, base=12 ... base=18 까지 base와 pointer가 가리키는 숫자가 일치하지 않기 때문에 base는 19까지 증가할 것이다.
base의 일의 자리가 pointer가 가리키는 숫자와 같기 때문에 pointer와 base가 모두 증가한다. (만약 base의 십의 자리와 일치하면 바로 base가 증가하는 것이 아니라 pointer만 증가하고 base의 일의 자리와 pointer가 가리키는 숫자를 확인한다.)
base가 20일 때 십의 자리 숫자와 pointer가 가리키는 숫자가 같기 때문에 pointer는 증가하게 되고, pointer가 입력 받은 숫자의 마지막을 가리키기 때문에 최소 N의 값은 20이 될 것이다.
코드
