파이썬으로 풀어보는 SWEA 5688. 세제곱근을 찾아라

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXVyCaKugQDFAUo

SW Expert Academy

 

 

내 풀이(소인수분해):

prime_nums = [2]
for i in range(3, 1000000):
    for p in prime_nums:
        if i < p**2:
            prime_nums.append(i)
            break
        if i % p == 0:
            break
    else:
        prime_nums.append(i)
 
for tc in range(1, int(input()) + 1):
    N = int(input())
    result = []
    ans = -1
    TF = True
    for p in prime_nums:
        if N == 1:
            break
 
        if N < p ** 3:
            TF = False
            break
 
        if N % p == 0:
            cnt = 1
            N //= p
 
            while N % p == 0:
                N //= p
                cnt += 1
 
            if cnt % 3 != 0:
                TF = False
                break
            else:
                result.append((p, cnt // 3))
 
    if TF:
        ans = 1
        for p, cnt in result:
            ans = ans * p ** cnt
 
    print("#%d"%(tc), ans)

실행시간: 478ms, 메모리: 63,652kb

소인수분해를 이용하면 세제곱근을 빠르게 찾을 수 있을 것이라는 기대와 달리 실행시간은 그리 빠르지 않았다.

 

내 풀이:

lst = [i**3 for i in range(1000001)]
for tc in range(1, int(input()) + 1):
    N = int(input())
    for i in range(1, 1000001):
        if N == lst[i]:
            ans = i
            break
        if N < lst[i]:
            ans = -1
            break
 
    print("#%d"%(tc), ans)

실행시간: 360ms, 메모리: 134,660kb

1부터 1000000의 세제곱수를 저장한 다음 앞에서부터 차례대로 비교하였다.

 

내 풀이:

lst = [i**3 for i in range(1000001)]
for tc in range(1, int(input()) + 1):
    N = int(input())
    low = 1
    high = 1000001
    val = 500000
 
    while True:
        if lst[val] > N:
            if val == (val + low) // 2:
                ans = -1
                break
            else:
                high = val
                val = (val + low) // 2
                continue
        elif lst[val] < N:
            if val == (val + high) // 2:
                ans = -1
                break
            else:
                low = val
                val = (val + high) // 2
                continue
        else:
            ans = val
            break
 
    print("#%d"%(tc), ans)

실행시간: 218ms, 메모리: 134,660kb

1부터 1000000의 세제곱수를 저장하는 방법은 동일하나 저장된 값을 탐색하는 알고리즘 이진탐색으로 개선하였다.

 

내 풀이:

for tc in range(1, int(input()) + 1):
    val = round(pow(int(input()), 1/3), 2)
    if val != int(val):
        val = -1
    print("#%d"%(tc), int(val))

실행시간: 154ms, 메모리: 58,940kb

제곱을 할 때 이용하는 pow() 내장함수를 이용하여 세제곱근 계산을 해주었다.