[Java] 백준 1676 팩토리얼 0의 개수

2024. 1. 11. 15:30· 코딩테스트/백준
목차
  1. 문제
  2. 입력
  3. 출력
  4. 풀이✔
  5. 결과
728x90

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초 128 MB 74708 35350 29587 47.045%

문제

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

입력

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

출력

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

풀이✔

1️⃣ 문제 분석하기

  • N! 에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때 까지 0의 개수를 구하는 프로그램을 작성해야 함.
  • 계산된 팩토리얼의 뒤에서부터 한 자리씩 확인합니다.
  • 0이 아닌 숫자가 나올 때까지 0의 개수를 세어줍니다.
  • 예를들어 10! ⇒ 3688800 이면은
    • → 0의 개수는 2개이다.
  • 팩토리얼의 값에서 0의 개수를 세는 로직을 짜는게 방법!

2️⃣ 요구 조건 구현하기

  • 첫째 줄에 N이 주어짐
  • N에 대한 0의 개수를 출력해야함.

3️⃣ 슈도 코드

Bufferedreader 생성
변수 N = 입력받기

long fact=  factorial(N);
int count = countZero(fact);

count 출력

countZero(int n) {
		로직 작성
}

 

4️⃣ 코드 작성

package Algorithm_step;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B1676 {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(bf.readLine());
		long fact = factoiral(N);
		int count = CountZero(fact);

		System.out.println(count);
	}

	//0세기
	private static int CountZero(long number) { //3688800
		int countZero = 0;

		while (number % 10 == 0) {
			countZero++;
			number /= 10;
		}

		return countZero;
	}

	//팩토리얼
	private static long factoiral(int n) {
		if(n<=1) {
			return 1;
		} else {
			return n * factoiral(n-1);
		}
	}
}
		while (number % 10 == 0) {
			countZero++;
			number /= 10;
		}

1번

number = 3628800

3628800 % 10 == 0(나머지)

성립이 되므로 countZero 1증가

3628800 / 10 = 362880

 

2번

number = 362880

362880 % 10 == 0(나머지)

성립이 되므로 countZero 1증가

362880/10 = 36288

 

3번

number = 36288

36288 % 10 == 8(나머지)

성립이 안된다.

while문 종료

 

이렇게 풀면은 문제 자체는 풀리지만 백준에서는 “시간 초과” 가 뜹니다.

그래서 다른 방법으로 접근을 해보았습니다.

 

애초에 접근을 0이 아닌 숫자가 나올 때 까지 0의 개수를 구하는 것 이니

중간에 0이 낀거는 상관 안써두 된다.

 

소인수 분해를 통해 풀 수 있었습니다.

10은 2*5 이다.

 

2는 5보다 작은 수여서 연속된 수를 곱하게 되면 자연스레 모든 값들의 소인수 분해들은 2의 개수가 5의 개수보다 많다.

기본적으로 5의 개수에 따라 0이 변화한다고 보면 된다.

그러므로 5를 나누면서 누적합을 구하는 로직을 짜야한다.

int count = 0;
 
while (num >= 5) {
	count += num / 5;
	num /= 5;
}

로직을 교체 해주고 팩토리얼을 따로 구하는 로직을 빼면 시간초과가 뜨지 않는다. 자세한건 아래 설명이 있습니다.

결과

package Algorithm_step;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B1676 {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(bf.readLine());
		int count = CountZero(N);

		System.out.println(count);
	}

	//0세기
	private static int CountZero(long number) { //3688800
		int countZero = 0;
 
		while (number >= 5) {
			countZero  += number/5;
			number/=5;
		}

		return countZero;
	}
}

사실상 팩토리얼을 구하고 또 계산을 할 필요도 없었습니다.

N이 10이라고 가정을 하면

10/5 ⇒ 2 , 바로 2가 0을 개수라고 생각하면 된다.

15/5 ⇒ 3, 3이 뒤에서 부터 센 0을 개수 이다.

ref : https://st-lab.tistory.com/165

 

위 사진에서 0의 개수를 파악하면서 알 수 있었습니다. 만약에

전체에 0을 개수를 세는 로직을 짜야했으면 다른 코드가 나왔을 것 입니다.

 

5️⃣ 핵심 파악하기

0을 구하거나, 몫 나머지 를 구하는 문제가 나온다면

%10, /10을 통해서 구하는 방법을 처음으로 떠올려야 하며

10을 소인수 분해시 2,5 라는 것을 염려해두고 이 방법을 활용한 로직 또한

생각을 해야 한다.

 

728x90
  1. 문제
  2. 입력
  3. 출력
  4. 풀이✔
  5. 결과
'코딩테스트/백준' 카테고리의 다른 글
  • [Java] 백준 9095 1,2,3 더하기
  • [Java]백준 1929 소수 구하기
  • [Java] 백준 10845 큐
  • [Java] 백준 10810 공 넣기
hyeon.q
hyeon.q
Backend Developer
hyeon.q
hyeonq.log
hyeon.q
전체
오늘
어제
  • 분류 전체보기 (133)
    • Java (30)
      • Java (20)
      • OOP (6)
      • 디자인패턴 (2)
    • 코딩테스트 (28)
      • 프로그래머스 (4)
      • 백준 (20)
      • 알고리즘 (2)
      • 자료구조 (2)
    • Spring (29)
      • Boot (23)
      • Core (2)
      • Test (1)
      • Security (2)
    • Database (16)
      • MySQL (4)
      • JPA (10)
      • Redis (2)
    • FE (2)
      • React (1)
    • CS (10)
      • Linux (3)
      • 네트워크 (4)
      • 운영체제(OS) (3)
    • Infra (4)
      • Jenkins (0)
      • Docker (2)
      • Nginx (2)
    • 개발방법론 (3)
      • TDD (1)
      • DDD (2)
    • Etc (11)
      • 리뷰 (2)
      • 회고 (8)
      • 핀테크 (1)

블로그 메뉴

  • Github

공지사항

인기 글

태그

  • SpringBoot
  • 프로그래머스
  • Java
  • 백준
  • spring
  • OOP
  • JPA
  • 객체지향
  • MySQL
  • 알고리즘

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
hyeon.q
[Java] 백준 1676 팩토리얼 0의 개수
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.