[알고리즘 문제 풀기] The Next Number (Small)(12645)

1. 문제 풀이 아이디어

• 백트래킹을 이용해 가능한 수를 오름차순으로 구성하면서 처음으로 주어진 수보다 큰 수를 찾는 순간 출력해 문제를 해결한다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder();

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int t = int.Parse(sr.ReadLine());
    for (int tt = 0; tt < t; tt++)
    {
        string input = "0" + sr.ReadLine();
        int[] num = new int[10];
        int count = 0;
        bool cur = false;
        StringBuilder sbn = new StringBuilder();
        foreach (char c in input) num[c - '0']++;
        Solve();
        bool Solve()
        {
            if (count == input.Length)
            {
                if (cur)
                {
                    sb.AppendLine($"Case #{tt + 1}: " + int.Parse(sbn.ToString()));
                    return true;
                }
                if (sbn.ToString().Equals(input))
                    cur = true;
                return false;
            }
            for (int i = 0; i < 10; i++)
            {
                if (num[i] == 0) continue;
                count++;
                num[i]--;
                sbn.Append(i);
                if (Solve())
                    return true;
                sbn.Remove(sbn.Length - 1, 1);
                num[i]++;
                count--;
            }
            return false;
        }
    }
    sw.Write(sb);
}

3. 정리

• "0" + input을 통해 자리 수 증가 문제를 방지하고 백트래킹으로 모든 경우를 사전순으로 탐색한다.

• 각 숫자의 등장 횟수를 세어 가능한 숫자만 조합할 수 있도록 배열 num을 사용한다.

• Solve() 함수는 재귀적으로 숫자를 하나씩 조합하면서 input보다 큰 수를 처음 발견했을 때 출력하고 종료한다.

• cur 플래그는 현재 조합된 숫자가 입력보다 큰 상태인지 나타내며, 처음으로 큰 수를 발견했을 때만 출력하도록 제어한다.

• int.Parse(sbn.ToString())로 앞의 0을 제거하고 정수 형태로 출력해 문제를 해결한다.