2312 수 복원하기

수 복원하기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1590	887	755	56.301%

문제

양의 정수 N이 주어졌을 때, 이 수를 소인수분해 한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다.

출력

각 테스트 케이스마다 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력한다. 출력 순서는 인수가 증가하는 순으로 한다.

소수를 구하는 문제다.

소수를 구하는 방법 중에서 무슨 로직이 있었던 것 같은데

오랜만이라 그런거 생각안하고 생각의 흐름대로 갔었더니 시간초과가 되었습니다.

당연한 결과겠죠?

아래는 그 소스입니다.

계속 시간초과가 뜨길래 소수중에서 각각이 몇개가 쓰여지는지 판별하는 로직이 문제인 줄 알았으나 그게 아니었습니다.

import sys

sys.stdin = open("input.txt", "r")

#=====================================================

def is_prime_number(num : int):

for i in range(2,int(num/2)+1):

if num%i == 0:

return False

return True

def how_much_use_this_num(body : int, prime_list : list):

count_list=[0] * len(prime_list)

cnt=0

while body != 1:

if body%prime_list[cnt] == 0:

body = body/prime_list[cnt]

count_list[cnt] = count_list[cnt] + 1

cnt = cnt+1

if cnt == len(prime_list):

cnt = 0

return count_list

#======================================================

T = int(input())

prime_number_list = []

for j in range(2, int(100000 ** 0.5)+1 ):

if is_prime_number(j):

prime_number_list.append(j)

for i in range(T):

N = int(input())

cnt_list = how_much_use_this_num(N, prime_number_list)

for c in range(len(cnt_list)):

if cnt_list[c] != 0:

print("{0} {1}".format(prime_number_list[c] , cnt_list[c] ))

그래서 복습도 할겸 어렴풋이 기억나는 그 알고리즘을 검색해보았습니다.

바로 에라토스테네스의 체 입니다. (이름부터 외우기가 어렵다.)

바로 위 소스에서 문제가 되었듯이

엄청나게 범위가 클때의 소수들을 제일 빠르게 구하는 알고리즘입니다.

저는 애초에 100000 까지의 소수들을 모두 찾는데 단순한 for 문을 썼으므로

그 뒤로 어떠한 로직을 짜더라도 시간초과가 뜰 수 밖에 없는 운명이었습니다.

그렇다면 소수들을 구하는 로직만 구현하면 되겠죠?

에라토스테네스의 체는 일정범위안의 소수를 찾을 때 쓴다.

일정한 범위 만큼의 bool형 배열을 선언해주고

인덱스 0,1 부분은 false (소수가 아니다) 처리를 미리 해줍니다.

왜냐하면 0,1 부분은 2배수를 하면 오히려 역효과가 나기 때문입니다.

number_list = [False, False] + [True]*(N+1)

이제 2부터 N+1까지 반복문을 돌려줍니다.

그때 iterator가 True인 부분을 발견하면

그 부분의 인덱스(i)의  *2인 인덱스부터 i간격으로 N+1까지 모두 False 처리를 해줍니다.

이 과정을 반복하면 됩니다.

아래는 소스코드입니다.

import sys

sys.stdin = open("input.txt", "r")

#=====================================================

def how_much_use_this_num(body : int, prime_list : list):

count_list=[0] * len(prime_list)

cnt=0

while body != 1:

if body%prime_list[cnt] == 0:

body = body/prime_list[cnt]

count_list[cnt] = count_list[cnt] + 1

cnt = cnt+1

if cnt == len(prime_list):

cnt = 0

return count_list

#======================================================

T = int(input())

number_list = [False, False] + [True] * (100000 -1)

prime_number_list=[]

for i in range(2, 100000 + 1):

if number_list[i]:

prime_number_list.append(i)

for j in range(2*i, 100000+1, i):

number_list[j] = False

for i in range(T):

N = int(input())

cnt_list = how_much_use_this_num(N, prime_number_list)

for c in range(len(cnt_list)):

if cnt_list[c] != 0:

print("{0} {1}".format(prime_number_list[c] , cnt_list[c] ))

얼핏 느끼기에는 2중 for문이고 일반 for문 처럼 결국엔 N만큼 다 순회하는거 아니냐,

근데 왜 처리 시간이 다르냐고 생각하실 수 있습니다.

하지만 이렇게 생각하면 됩니다.

여러분 앞에 1부터 100000까지의 숫자카드가 있습니다.

여러분들은 카드를 하나씩 집어가며 그 숫자가 소수인지 나누어가며 판별할 것인가요?

아니면

소수인 카드를 고르고 그 소수의 배수인 카드를 보지도 않고 위치만 찝어서

 쫘르르르륵 한번에 없애가며 소수를 판별해 나갈 것인가요?