반응형
💻 Problem
1949 년 인도 수학자 Kaprekar는 Kaprekar 연산을 고안해 냈다. Kaprekar 연산은 네 자릿수 중 모든 자릿수가 같지 않은 수(1111, 2222 등을 제외한)의 각 자리의 숫자를 재배열해서 만들 수 있는 가장 큰 수와 가장 작은 수를 만들어서 그 차이를 계산하는데, 그 결과로 나온 새로운 숫자를 갖고 같은 과정을 반복하는 것이다.
간단한 연산이지만 Kaprekar는 이 연산이 놀라운 결과를 보여준다는 것을 발견했다. 올해 연도인 2008로 그 결과를 알아보자. 2008로 만들 수 있는 가장 큰 수는 8200이고 가장 작은 수는 0028이다.
- 8200 – 0028 = 8172
- 8721 – 1278 = 7443
- 7443 – 3447 = 3996
- 9963 – 3699 = 6264
- 6642 – 2466 = 4176
- 7641 – 1467 = 6174
- 7641 – 1467 = 6174
6174에 도달한 다음에는 매번 6174를 만들어 낸다. 2008 만이 유독 6174에 도달하는 것이 아니라 한 숫자로 이루어지지 않은 모든 네 자릿수는 Kaprekar 연산을 통해 6174로 가게 된다. 2008의 경우 6 단계를 거쳐 6174로 가게 되었는데, 다른 숫자가 입력으로 주어졌을 때 몇 단계만에 6174로 가는지 알아내는 프로그램을 작성하시오.
💡 Approach
처음에 시간 초과가 떠서 푸는 방식이 잘못된 줄 알았다.
이게 그렇게 오래 걸리나? 싶었는데 함정 케이스가 있던 것이었다.
예를 들어, `1000`과 같은 조합의 숫자가 오면
- 1000 - 0001 = 999
- 999 - 999 = 0
- ...
이렇게 무한 루프에 빠져버린다..
그래서 시간 초과가 뜨는 것이었다.
따라서 저런 경우에는 0을 추가해 줘야 한다.
- 1000 - 0001 = 0999
- 9990 - 0999 = 8991
- 9981 - 1899 = 8082
- 8820 - 0288 = 8532
- 8532 - 2358 = 6174
이렇게 오도록 말이다!
✏️ Solution
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
num = input().rstrip()
cnt = 0
while num != '6174':
min_num = ''.join(sorted(num))
max_num = min_num[::-1]
num = str(int(max_num) - int(min_num))
if len(num) < 4:
num = '0' * (4 - len(num)) + num
cnt += 1
print(cnt)
반응형