[SWEA][D4][#05688] 세제곱근을 찾아라

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

양의 정수 N에 대해 N = \({X}^{3}\)가 되는 양의 정수 X 를 구하여라.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1≤N≤\({10}^{18}\)) 이 주어진다.

출력

각 테스트 케이스마다 첫 번째 줄에는‘#T’(T는 테스트케이스 번호를 의미하며 1부터 시작한다.)를 출력하고, N = \({X}^{3}\)가 되는 양의 정수 X를 출력한다.

만약 이런 X가 존재하지 않으면 -1을 출력한다.

예제

입력

3
27
7777
64

출력

#1 3
#2 -1
#3 4

My Sol A : 단순 반복

T = int(input())
for tc in range(1, T+1):
    N = int(input())

    k = 1
    while k**3 < N:
        k += 1

    ans = k if k**3==N else -1
    print(f'#{tc} {ans}')

N은 최대 \({10}^{18}\)이므로 X는 최대 \({10}^{6}\)이다. 10만까지는 1씩 올라도 그렇게 오래 걸리지 않을 것이라는 판단으로 1씩 올려 세제곱해보며 값이 N과 같거나 넘어서는 순간 1을 올리는 반복을 중단하고 세제곱을 한 값이 N과 정확히 일치하는지 확인한다. 정확히 일치하면 반복횟수를 출력하고, 아니라면 -1을 출력한다.

아무래도 최대 10만번의 연산을 하는만큼 272ms의 실행시간이 걸렸다.

My Sol B : 이분 탐색

def bisearch(start, end, N):

    while start <= end:
        mid = (start+end)//2
        if mid**3 == N:
            return mid
        elif mid**3 < N:
            start = mid+1
        else:
            end = mid-1
    return -1

T = int(input())
MAX_VAL = 10**6
for tc in range(1, T+1):
    N = int(input())

    if N==1:
        ans = 1
    elif N==10**18:
        ans = 10**6
    else:
        ans = bisearch(1, MAX_VAL, N)
    print(f'#{tc} {ans}')

시작값은 1, 끝값을 \({10}^{6}\)으로 하여 범위를 반씩 잘라 좁혀가며 원하는 값을 찾는 이분 탐색을 사용하였다. 주목할 점은 3가지 경우로 나누어 mid가 정확히 원하는 값이라면 해당 mid를 가지고 반환하고, 앞의 범위라면 end를 mid-1로, 뒤의 범위라면 start를 mid+1로 재설정하여 다시 반복을 하는 점이다. 나는 이분탐색을 사용할 때 항상 이 인덱스 범위를 설정하는 것에 대한 헷갈림을 겪는데, 공부했던 내용을 복습해보면 이 템플릿이 가장 효과적인 것 같다.

아무튼 범위를 반씩 줄여서 O(log N)의 시간복잡도로 연산 시간을 확 줄일 수 있었다. 151ms의 연산 시간을 보였다.

결과

PASS