백준 - 팩토리얼 진법[5692]

이번 포스팅에서는 백준 알고리즘의 팩토리얼 진법[5692] 코딩테스트 연습 문제를 풀어봅니다.

문제 설명

상근이는 보통 사람들이 사는 것과는 조금 다른 삶을 사는 사람이다. 상근이는 이런 사람들의 시선이 부담스럽기 때문에, 자신만의 숫자를 개발하기로 했다. 바로 그 이름은 팩토리얼 진법이다. 팩토리얼 진법은 각 자리에 올 수 있는 숫자는 0부터 9까지로 10진법과 거의 비슷하다. 하지만, 읽는 법은 조금 다르다. 팩토리얼 진법에서는 i번 자리의 값을 ai×i!로 계산한다. 즉, 팩토리얼 진법에서 719는 10진법에서 53과 같다. 그 이유는 7×3! + 1×2! + 9×1! = 53이기 때문이다.

팩토리얼 진법으로 작성한 숫자가 주어졌을 때, 10진법으로 읽은 값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 최대 5자리인 팩토리얼 진법 숫자가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 팩토리얼 진법 숫자를 10진법으로 읽은 값을 출력한다.

입출력 예

입력	출력
719 1 15 110 102 0	53 1 7 8 8

문제 풀이

입력 받은 숫자를 리스트로 분할하여 앞자리 부터 (리스트 갯수 - i)수를 구해서 팩토리얼 연산을 분할된 값과 곱해서 모두 더해주면 결과가 나옵니다.

팩토리얼 연산을 제귀 함수 또는 반복문으로 구할 수 있지만 파이썬은 팩토리얼 함수도 이미 구현이 되어 있습니다. 팩토리얼 함수를 사용하여 구현하면 아래와 같이 간단히 구현이 가능합니다.

import sys, math

# 입력
while True:
    num = sys.stdin.readline().strip() # input()은 시간초과가 나옴
    if num == '0':
        break
    else:
        n = list(map(int, list(num)))
        nlen = len(n)
        sum = 0
        for i in range(nlen):
            sum += n[i] * math.factorial(nlen-i) # math.factorial() 함수를 이용
        print(sum)

[입력]
719
1
15
110
102
0
[출력]
53
1
7
8
8

팩토리얼 함수를 직접 구현 할 수도 있지만 구현해서 사용시 백준 사이트에서 시간초과의 늪에 빠질 수 있음으로 따로 구현 하진 않았습니다.

결과는 아래와 같이 잘 통과 되는 것을 확인 할 수 있습니다.