BOJ 9047번 - 6174

[백준 온라인 저지 링크]

9047번: 6174

기초 테스트 문제로 올라와 풀어본 문제였는데, 생각보다 까다로운 문제였습니다.

숫자 문자열의 (내림차순 정렬 결과) - (오름차순 정렬 결과)를 계속 구해주면 간단하게 답을 찾을 것 같지만...

틀렸을리 없어! 채점 서버 오류일거야!!

아무 생각 없이 덤비면 피로 얼룩진 결과창을 보게 됩니다.

시간 초과의 이유는 바로 1000과 9998 두 개의 케이스 때문으로, 두 케이스는 다음 결과를 얻게 됩니다.

(+ 이 둘은 제가 발견한 일부로, 찾지 못한 케이스가 더 있을수도 있습니다!)

[함정 케이스 1. 1000]

1000 - 0001 = 999

999 - 999 = 0 => 무한 루프

[함정 케이스 2. 9998]

9998 - 8999 = 999

999 - 999 = 0 => 무한 루프

 

바로 이래서 시간 초과를 만나게 되는 건데요, 따라서 연산 결과 문자열이 4자리 미만일 경우에는 앞에 "0" 을 채워주는 작업이 필요합니다.

[정답 코드 - Python]

T = int(input())

for i in range(T):
    ans = 0
    S = input()

    while S != "6174":
        s_bigger = int(''.join(sorted(S, reverse=True)))
        s_smaller = int(''.join(sorted(S)))
        S = str(s_bigger - s_smaller)

        if len(S) < 4:
            temp = ""
            for i in range(4 - len(S)):
                temp += '0'
            S = temp + S

        ans += 1

    print(ans)

+ 여담이지만 문제의 Kaprekar 연산이 매우 신기했던 문제입니다.

소개팅할때 풀기 좋은 썰이 될 듯 하네요 ✦‿✦