0 이상 10^d 미만인 정수 x로 시작해서 다음 일을 되풀이한다.
지금 수를 앞에 0을 채워 꼭 d자리로 쓴 다음, 그 숫자들을 큰 것부터 늘어놓은 수에서 작은 것부터 늘어놓은 수를 뺀다. 뺀 값이 다음 수다.
예를 들어 d = 4이면 2111은 2111 − 1112 = 999가 된다. 999는 0999로 써서 9990 − 0999 = 8991이 된다.
이렇게 얻는 수를 차례로 a0 = x, a1, a2, …라고 하자.
앞에 0을 채운 d자리 수는 10^d개뿐이므로 언젠가 앞에서 나온 수가 다시 나온다.
앞에서 나온 수가 처음으로 다시 나오는 때를 aj라 하고, 그 수가 처음 나왔던 때를 ai(i < j)라 하자.
몇 걸음 만에 끝날지 미리 알 수 없으니, 반복은 while 문으로 돈다.
입력의 줄마다 i, j − i, 그리고 고리를 이루는 수 ai, a(i+1), …, a(j−1) 가운데 가장 작은 수를 한 줄에 빈칸 하나로 띄워 출력하라.
가장 작은 수는 앞에 0을 붙이지 않은 보통의 정수로 출력한다.
입력
첫 줄에 T(1 ≤ T ≤ 1000). 다음 T줄에 d와 x(2 ≤ d ≤ 10, 0 ≤ x < 10^d). x는 앞에 0 없이 주어진다.
출력
T줄. 줄마다 "i j−i 가장작은수"
예시 1 · stdin
4
4 3524
4 2111
4 1111
2 9
stdout
3 1 6174
5 1 6174
1 1 0
0 5 9
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
몇 번 돌지 모르는 반복은 while이에요. Python while a not in seen:, C·C++·Java·C#·JavaScript·TypeScript while (...), 크레이콘 동안 (조건) { }. 반복을 멈출 조건은 '이 수를 전에 본 적이 있나'이고, 수 → 처음 나온 걸음 번호를 사전에 적어 두면 바로 i를 알 수 있어요(Python dict, JS·TS Map, Java HashMap<Long, Integer>, C# Dictionary<long, int>, C++ std::map, 크레이콘 사전()과 있나). C에는 사전이 없지만, d ≤ 10이면 나오는 수가 서른 개를 넘지 않아서 배열을 처음부터 훑어도 충분해요. 함정 넷: ① 수를 문자열로 바꾸면 앞의 0이 사라져요. 0999를 세 자리 999로 다루면 999 − 999 = 0으로 끝나 버려요. Python str(a).zfill(d), JS·TS String(a).padStart(d, "0"), Java String.format("%0" + d + "d", a), C# a.ToString().PadLeft(d, '0'), 크레이콘 ("" + a).앞채우기(d, "0")처럼 채우거나, C처럼 % 10으로 꼭 d번 떼어 내면 0도 세어져요. ② d = 10이면 9876543210처럼 int(약 21억)를 넘는 수가 나와요. C·C++은 long long, Java·C#은 long이 필요하고, Java의 Integer.parseInt는 그런 수에서 예외를 내요. Python은 정수 크기에 끝이 없고, JS·TS·크레이콘의 수는 2^53까지 정확해서 그대로 돼요. ③ '바로 앞 수와 같으면 멈춤'으로 쓰면 6174처럼 제자리에 서는 수에서만 멈춰요. d = 2에서는 09 → 81 → 63 → 27 → 45 → 09처럼 다섯 수가 돌아서 반복이 끝나지 않아요. ④ 다시 나온 때 j를 걸음 수로 적기 쉬워요. 묻는 것은 고리에 들어가기 전의 걸음 수 i예요.
Pythonmain.py · 19 줄
def step(a, d): s = str(a).zfill(d) # 앞에 0을 채워 꼭 d자리로 big = int("".join(sorted(s, reverse=True))) small = int("".join(sorted(s))) return big - smallt = int(input())for _ in range(t): d, x = map(int, input().split()) first_seen = {} # 수 → 처음 나온 걸음 번호 a, k = x, 0 while a not in first_seen: first_seen[a] = k a = step(a, d) k += 1 i = first_seen[a] loop = [v for v, at in first_seen.items() if at >= i] print(i, k - i, min(loop))
JavaScriptmain.js · 28 줄
const lines = require("fs").readFileSync(0, "utf8").trim().split("\n");function step(a, d) { const digits = String(a).padStart(d, "0").split(""); // 앞에 0을 채워 꼭 d자리로 digits.sort(); const small = Number(digits.join("")); const big = Number(digits.reverse().join("")); return big - small;}const t = Number(lines[0]);const out = [];for (let c = 1; c <= t; c++) { const [d, x] = lines[c].trim().split(" ").map(Number); const firstSeen = new Map(); // 수 → 처음 나온 걸음 번호 let a = x; let k = 0; while (!firstSeen.has(a)) { firstSeen.set(a, k); a = step(a, d); k++; } const i = firstSeen.get(a); let min = Infinity; for (const [v, at] of firstSeen) if (at >= i) min = Math.min(min, v); out.push(`${i} ${k - i} ${min}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 29 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").trim().split("\n");function step(a: number, d: number): number { const digits: string[] = String(a).padStart(d, "0").split(""); // 앞에 0을 채워 꼭 d자리로 digits.sort(); const small = Number(digits.join("")); const big = Number(digits.reverse().join("")); return big - small;}const t = Number(lines[0]);const out: string[] = [];for (let c = 1; c <= t; c++) { const [d, x] = lines[c].trim().split(" ").map(Number); const firstSeen = new Map<number, number>(); // 수 → 처음 나온 걸음 번호 let a = x; let k = 0; while (!firstSeen.has(a)) { firstSeen.set(a, k); a = step(a, d); k++; } const i = firstSeen.get(a)!; let min = Infinity; for (const [v, at] of firstSeen) if (at >= i) min = Math.min(min, v); out.push(`${i} ${k - i} ${min}`);}console.log(out.join("\n"));
JavaMain.java · 41 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.HashMap;import java.util.Map;public class Main { // 10자리 수(9,876,543,210)는 int(약 21억)를 넘어서 long으로 센다 static long step(long a, int d) { char[] digits = String.format("%0" + d + "d", a).toCharArray(); // 앞에 0을 채워 꼭 d자리로 Arrays.sort(digits); long small = Long.parseLong(new String(digits)); long big = Long.parseLong(new StringBuilder(new String(digits)).reverse().toString()); return big - small; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int c = 0; c < t; c++) { String[] p = in.readLine().trim().split(" "); int d = Integer.parseInt(p[0]); long a = Long.parseLong(p[1]); Map<Long, Integer> firstSeen = new HashMap<>(); // 수 → 처음 나온 걸음 번호 int k = 0; while (!firstSeen.containsKey(a)) { firstSeen.put(a, k); a = step(a, d); k++; } int i = firstSeen.get(a); long min = Long.MAX_VALUE; for (Map.Entry<Long, Integer> e : firstSeen.entrySet()) if (e.getValue() >= i) min = Math.min(min, e.getKey()); out.append(i).append(' ').append(k - i).append(' ').append(min).append('\n'); } System.out.print(out); }}
C#Main.cs · 42 줄
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ // 10자리 수(9,876,543,210)는 int(약 21억)를 넘어서 long으로 센다 static long Step(long a, int d) { char[] digits = a.ToString().PadLeft(d, '0').ToCharArray(); // 앞에 0을 채워 꼭 d자리로 Array.Sort(digits); long small = long.Parse(new string(digits)); Array.Reverse(digits); long big = long.Parse(new string(digits)); return big - small; } static void Main() { int t = int.Parse(Console.ReadLine().Trim()); var out_ = new StringBuilder(); for (int c = 0; c < t; c++) { string[] p = Console.ReadLine().Trim().Split(' '); int d = int.Parse(p[0]); long a = long.Parse(p[1]); var firstSeen = new Dictionary<long, int>(); // 수 → 처음 나온 걸음 번호 int k = 0; while (!firstSeen.ContainsKey(a)) { firstSeen[a] = k; a = Step(a, d); k++; } int i = firstSeen[a]; long min = firstSeen.Where(e => e.Value >= i).Min(e => e.Key); out_.Append($"{i} {k - i} {min}\n"); } Console.Write(out_); }}
C++main.cpp · 37 줄
#include <algorithm>#include <iostream>#include <map>#include <string>// 10자리 수(9,876,543,210)는 int(약 21억)를 넘어서 long long으로 센다long long step(long long a, int d) { std::string s = std::to_string(a); s.insert(0, d - s.size(), '0'); // 앞에 0을 채워 꼭 d자리로 std::sort(s.begin(), s.end()); long long small = std::stoll(s); std::reverse(s.begin(), s.end()); long long big = std::stoll(s); return big - small;}int main() { int t; std::cin >> t; while (t--) { int d; long long a; std::cin >> d >> a; std::map<long long, int> firstSeen; // 수 → 처음 나온 걸음 번호 int k = 0; while (!firstSeen.count(a)) { firstSeen[a] = k; a = step(a, d); k++; } int i = firstSeen[a]; long long min = -1; for (const auto& [v, at] : firstSeen) if (at >= i) { min = v; break; } // map은 작은 수부터 돈다 std::cout << i << ' ' << k - i << ' ' << min << '\n'; }}
Cmain.c · 40 줄
#include <stdio.h>/* 10자리 수(9,876,543,210)는 int(약 21억)를 넘어서 long long으로 센다 */long long step(long long a, int d) { int count[10] = {0}; for (int i = 0; i < d; i++) { /* 꼭 d번 떼어 내면 앞자리 0도 센다 */ count[a % 10]++; a /= 10; } long long big = 0, small = 0; for (int g = 9; g >= 0; g--) for (int r = 0; r < count[g]; r++) big = big * 10 + g; for (int g = 0; g <= 9; g++) for (int r = 0; r < count[g]; r++) small = small * 10 + g; return big - small;}int main(void) { int t; scanf("%d", &t); while (t--) { int d; long long a; scanf("%d %lld", &d, &a); long long seen[64]; /* 나온 수를 차례대로(d ≤ 10이면 30개를 넘지 않는다) */ int k = 0, i = -1; while (1) { for (int s = 0; s < k; s++) if (seen[s] == a) i = s; if (i >= 0) break; seen[k++] = a; a = step(a, d); } long long min = seen[i]; for (int s = i; s < k; s++) if (seen[s] < min) min = seen[s]; printf("%d %d %lld\n", i, k - i, min); } return 0;}
Craykonmain.cray · 40 줄
// 한 걸음: 앞에 0을 채워 꼭 d자리로 쓰고, 큰 것부터 늘어놓은 수 − 작은 것부터 늘어놓은 수한걸음(a, d){ s = ("" + a).앞채우기(d, "0"); digits = []; 각각 (ch 에서 s) { digits.넣기(ch); } digits.정렬(); small = digits.잇기("").수로변환(); digits.뒤집기(); big = digits.잇기("").수로변환(); 돌려주기 big - small;}t = 콘솔.줄읽기().공백제거().수로변환();반복 (c = 0; c < t; c++){ p = 콘솔.줄읽기().공백제거().나누기(" "); d = p[0].수로변환(); a = p[1].수로변환(); firstSeen = 사전(); // 수 → 처음 나온 걸음 번호 order = []; // 나온 차례대로 k = 0; 동안 (!firstSeen.있나(a)) { firstSeen[a] = k; order.넣기(a); a = 한걸음(a, d); k += 1; } i = firstSeen[a]; least = order[i]; 반복 (s = i; s < k; s++) { least = 수학.작은수(least, order[s]); } 콘솔.쓰기(i + " " + (k - i) + " " + least);}