[파이썬/Python] 백준 1676번 팩토리얼 0의 개수

[파이썬/Python] 백준 1676번 팩토리얼 0의 개수

1676번: 팩토리얼 0의 개수

---

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

예제 입력

10

예제 출력

2

풀이 1

int 로 판별

import sys
input = sys.stdin.readline

def factorial(n):
    result = 1
    for item in range(1, n+1):
        result *= item
    return result

# 입력값으로 주어진 팩토리얼을 계산하여 숫자 리스트로 변환
n = list(map(int, str(factorial(int(input())))))

count = 0

# 뒤에서부터 숫자를 탐색하면서 0의 개수를 세기 위한 반복문
for i in reversed(n):
    if not i:
        count += 1
    else:
        print(count)  # 처음으로 0이 아닌 숫자가 나왔을 때 0의 개수를 출력
        break

factorial(n) 함수의 시간 복잡도는 O(n)이다. n까지의 모든 수에 대해 반복문을 수행하므로, 팩토리얼을 계산하는 데는 O(n)의 시간이 소요된다.

n = list(map(int, str(factorial(int(input())))))의 시간 복잡도는 O(nlogn)이다. 입력값으로 주어진 N을 정수로 변환하고, 팩토리얼을 계산하여 문자열로 변환한 후 각 자리 숫자를 리스트로 저장하는 과정은 O(n)이다. 그러나 리스트 변환에 O(logn)의 시간이 소요된다. 이는 정수를 문자열로 변환하는 과정에서 자릿수(logn)에 따라 시간이 증가하기 때문이다.

for i in reversed(n):의 시간 복잡도는 O(n)이다. 리스트 n을 뒤에서부터 탐색하는 반복문이므로, 리스트의 길이인 n에 비례하는 시간이 소요된다.

따라서, 총 시간 복잡도는 O(n + nlogn) = O(nlogn)이다. 입력값 N에 따라 팩토리얼을 계산하고, 그 결과를 탐색하여 0의 개수를 구하는 과정이 수행된다.

풀이 2

str 로 판별

a = int(input())

summing = 1
count = 0
tt = -1

for i in range(1, a+1):
    summing *= i  # 1부터 a까지의 수를 차례로 곱하여 팩토리얼을 계산

while True:
    summing = str(summing)  # 팩토리얼 값을 문자열로 변환
    if summing[tt] == '0':  # 문자열을 역순으로 탐색하면서 현재 자리의 숫자가 0인지 확인
        count += 1 
        tt -= 1  # 인덱스 변수를 업데이트
    else:
        break  # 0이 아닌 숫자가 나왔을 때, 반복문을 종료

print(count)  # 0의 개수를 출력

for i in range(1, a+1): 부분은 O(a)의 시간이 소요된다.
while True: 부분에서는 문자열을 역순으로 탐색하므로, 문자열의 길이에 비례하는 시간이 소요된다. 따라서, 시간 복잡도는 O(log(N!))이다. 팩토리얼 값을 계산한 뒤에 문자열로 변환하여 탐색하기 때문에 팩토리얼의 자리수에 따라 시간이 결정된다. 일반적으로 N!의 자리수는 O(NlogN)이므로 O(log(N!))으로 표기할 수 있다.

풀이 3

팩토리얼 규칙으로 판별

N = int(input())

# N!에서 5로 나눈 몫, 25로 나눈 몫, 125로 나눈 몫을 구하여 더함
count = N // 5 + N // 25 + N // 125

print(count)

위 코드는 주어진 입력값 N에 대하여 N!에서 0의 개수를 구하는 방법 중 하나인 규칙을 이용한 코드이다.

N // 5: N!에서 5의 배수의 개수를 구한다. 5의 배수는 1부터 N까지의 수 중에서 5, 10, 15, 20, ...과 같이 5로 나누어떨어지는 수이다.
N // 25: N!에서 25의 배수의 개수를 구한다. 25의 배수는 1부터 N까지의 수 중에서 25, 50, 75, 100, ...과 같이 25로 나누어떨어지는 수이다.
N // 125: N!에서 125의 배수의 개수를 구한다. 125의 배수는 1부터 N까지의 수 중에서 125, 250, 375, 500, ...과 같이 125로 나누어떨어지는 수이다.
이렇게 구한 5의 배수, 25의 배수, 125의 배수의 개수를 합산하여 전체 0의 개수를 구한다.

코드는 상수 시간 내에 실행된다. 따라서 시간 복잡도는 O(1)이다.

 

참고자료

로그인

로그인

반응형

저작자표시

'Solved.ac - Python > CLASS 2' 카테고리의 다른 글

[파이썬/Python] 백준 18110번 solved.ac  (0)	2023.06.08
[파이썬/Python] 백준 11651번 좌표 정렬하기 2  (0)	2023.05.24
[파이썬/Python] 백준 15829번 Hashing  (0)	2023.05.24
[파이썬/Python] 백준 18111번 마인크래프트  (0)	2023.05.23
[파이썬/Python] 백준 10989번 수 정렬하기 3  (0)	2023.05.21

'Solved.ac - Python/CLASS 2' Related Articles

• [파이썬/Python] 백준 18110번 solved.ac 2023.06.08
• [파이썬/Python] 백준 11651번 좌표 정렬하기 2 2023.05.24
• [파이썬/Python] 백준 15829번 Hashing 2023.05.24
• [파이썬/Python] 백준 18111번 마인크래프트 2023.05.23

more

Comments