어떤 자연수 A가 주어진다. 여기에 자연수 B를 곱한 결과가 거듭제곱수가 되는 최소의 B를 구하는 프로그램을 작성하라.
입력
- 첫 번째 줄에 테스트 케이스의 수 T 가 주어진다.
- 각 테스트 케이스의 첫 번째 줄에는 하나의 자연수 A(1≤A≤10**7) 가 주어진다.
시간초과로 많은 어려움을 겪었던 문제...
1차시도 - 시간초과
문제의 난이도가 높지 않아 단순하게 2부터 A까지 나누었을 때 나눈 횟수가 홀수이면 곱해주는 방식으로 정답을 도출하려 하였다.
T = int(input())
for tc in range(T):
A = int(input())
res = 1
# items = dict()
for i in range(2, A+1):
if not A%i:
cnt = 1
A //= i
while True:
if not A%i:
cnt += 1
A //= i
else:
break
if cnt % 2:
res *= i
if A == 1:
break
print('#{} {}'.format(tc+1, res))
자연수 A의 범위가 10**7 까지이다 보니 큰 숫자의 경우 위의 방법은 시간초과가 발생하여 오답!
※ 평균적으로 100000개의 테스트 케이스 중 190개가 통과하였다...
2차시도 - 시간초과
혹시나해서 나누는 작업을 하지 않고 단순히 숫자를 증가시키면서 제곱수면 출력하도록 아래와 같이 코드를 작성해보았다.
import math
T = int(input())
for tc in range(T):
A = int(input())
for i in range(1, A+1):
if A * i == int(math.sqrt(A * i)) ** 2:
print('#{} {}'.format(tc+1, i))
break
예상대로 시간초과가 발생하였고 첫번째 방법보다 훨씬 적은 60개 가량의 테스트 케이스가 통과되었다.
3차시도 - 해결
모든 테스트 케이스에서 1부터 A까지의 범위의 반복문을 돌리는 것이 시간초과의 원인이라고 생각하였다.
따라서, 소수에 대해서만 A가 나누어떨어지는지 확인하려고 했다.
ex) 2로 나눈 이후에는 4, 6, 8.. 과 같은 짝수는 나누어질 수가 없다.
모든 테스트 케이스마다 반복해서 소수를 구하는 것은 비효율적이므로 가장 상단에 2부터 3162( = int(10000000 ** 0.5))까지의 소수를 담은 리스트를 만든다.
A 값이 제곱수이면 더 이상 진행할 필요가 없지만 제곱수가 아니라면 prime에 있는 소수값들로 하나씩 A값이 나누어지는지 확인한다.
→ 제곱수를 만들기 위한 값을 파악
나누어떨어지는 경우 A가 소수 p에 대해서 몇 번을 나눌 수 있는지 개수를 파악한다.
이후 cnt의 값이 짝수면 제곱근이 될 수 있지만 홀수면 해당 소수를 곱해줘야 제곱근이 되므로 res에 해당 소수(p)를 곱해준다
시간을 줄이기 위해서 A가 더 나누어 떨어질 수 없는 다음의 두 가지 경우는 break해준다.
1. A == 1
2. p > A
prime에 있는 모든 소수로 나누었음에도 나누어떨어지지 않았다면 해당 값은 prime의 최대값보다 더 큰 소수값이므로 res에 곱해준다.
코드는 아래와 같다
prime = [2]
for i in range(3, int(10000000 ** (0.5)), 2):
for p in prime:
if not i % p: break
else:
prime.append(i)
answer = []
T = int(input())
for tc in range(T):
A = int(input())
res = 1
if A**0.5 != int(A**0.5):
for p in prime:
cnt = 0
while not A % p:
A //= p
cnt += 1
if cnt % 2:
res *= p
if A == 1 or p > A:
break
if A > 1:
res *= A
answer.append('#{} {}'.format(tc+1, res))
for ans in answer:
print(ans)
사실 위의 알고리즘으로만 작성해도 될 것 같은데 테스트 케이스가 10만개다보니 반복문을 통한 출력문에서 상당한 시간을 잡아먹는다.
이럴 경우 하나의 리스트에 결과값을 전부 담은 다음 하나씩 출력해주면 시간을 단축할 수 있다.
✔ 문제를 풀고 난 후...
알고리즘 문제를 푸는 웹 사이트들이 많은데(Programmers, 백준, SWEA 등)
각 사이트에서 제출하는 방식이 다르다보니 어려움을 겪을 때가 있다.
※ 문제 스타일도... 많이 다른것 같다.
ex)
위 문제에서도 ans에 출력하는 내용을 담아 한 번에 출력함으로서 시간초과를 해결했다.
백준에서도 빠른 입력을 받을 수 있도록 sys.stdin.readline()
사용을 요구하는 문제가 있었다.
물론 파이썬에서 빠른 입출력을 공부하는 것도 좋지만
알고리즘 문제에서 시간초과는 단순 입출력이 아닌
알고리즘 과정에서의 시간 복잡도만 다뤘으면 좋겠다..😂