[BAEKJOON] 백준 1515: 수 이어 쓰기 (C#)

문제 링크

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

 

 

문제

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

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

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

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

 

 

입력

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

 

 

출력

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

 

 

통과한 답안

using System.Text;

namespace _1515
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string input = Console.ReadLine();
            int targetLength = input.Length;
            int curNumber = 1;
            int inputIdx = 0;

            while (inputIdx < targetLength)
            {
                string curString = curNumber.ToString();

                foreach (char c in curString)
                {
                    if (c == input[inputIdx])
                    {
                        inputIdx++;
                        if (inputIdx == targetLength)
                        {
                            break;
                        }
                    }
                }

                curNumber++;
            }

            Console.WriteLine(curNumber - 1);
        }
    }
}

 

그리디 알고리즘을 이용한 풀이 방법으로

1부터 시작하는 숫자를 가지고 input 값에 있는 숫자가 있는지 확인한다.

 

다시 말해서 input[0]에 표시된 숫자가 curNumber에 있는 숫자와 같다면

input[0]의 숫자는 확인한 것으로 하고 inputIdx를 늘리는 것으로 다음 숫자로 넘어간다.

 

이를 반복하여 input의 모든 숫자를 확인하는 방식으로 while 문을 작성하고

출력은 curNumber가 1이 추가 되었으므로 다시 1을 빼서 출력한다.