[백준] 2992 - 크면서 작은 수

1. 문제

2992번: 크면서 작은 수

2. 개요

정수 X가 주어졌을 때, 정수 X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

0 ~ 9까지의 배열을 만들어 X의 모든 숫자의 개수를 저장해둔다.

위를 이용하여 백트래킹으로 X와 같은 구성인 수 s를 가장 작은 수부터 모두 만들어본다.

s가 X이하라면 건너뛴다. X이상이면서 answer가 아직 갱신되지 않았다면 answer를 s로 갱신한다.

최종적으로 answer가 갱신되지 않았다면 0을 갱신되었다면 answer를 출력한다.

3-2. Python

import sys

nums = [0 for i in range(10)]

X = sys.stdin.readline().rstrip()

for i in range(len(X)):
    nums[int(X[i])] += 1

answer = ""

def BT(idx = 0, s = ""):
    global answer
    if idx == len(X) and answer == "":
        if s <= X:
            return

        else:
            answer = s

    for i in range(10):
        if nums[i] > 0:
            nums[i] -= 1
            BT(idx + 1, s + str(i))
            nums[i] += 1

BT()

if answer:
    print(answer)

else:
    print(0)

3-3. C#

namespace boj_2992
{
    internal class Program
    {
        static string X;
        static string answer;
        static int[] nums;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            X = sr.ReadLine().TrimEnd();

            nums = new int[10];

            for (int i = 0; i < X.Length; i++)
            {
                nums[int.Parse(X[i].ToString())]++;
            }

            answer = "";

            BT();

            if (answer == "")
                sw.WriteLine(0);

            else
                sw.WriteLine(answer);

            sw.Close();
        }

        static void BT (int idx = 0, string s = "")
        {
            if (idx == X.Length && answer == "")
            {
                if (int.Parse(s) <= int.Parse(X))
                    return;

                answer = s;
            }

            for (int i = 0; i < 10; i++)
            {
                if (nums[i] > 0)
                {
                    nums[i]--;
                    BT(idx + 1, s + i.ToString());
                    nums[i]++;
                }
            }
        }
    }
}