세제곱근을 찾아라 Python(SW Expert Academy)

난이도 : D3

문제번호 : 5688

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXVyCaKugQDFAUo&categoryId=AWXVyCaKugQDFAUo&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

양의 정수 N에 대해 N = X3가 되는 양의 정수X 를 구하여라.

입력

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

출력

각 테스트 케이스마다 첫 번째 줄에는‘#T’(T는 테스트케이스 번호를 의미하며 1부터 시작한다.)를 출력하고, N = X3가 되는 양의 정수 X를 출력한다. 만약 이런 X가 존재하지 않으면 -1을 출력한다.

예시

입력	출력
3 27 7777 64	#1 3 #2 -1 #3 4

---

2. 문제풀이

10^18 까지의 수를 찾아야 하므로 10^6+1까지의 리스트를 만들었다. 리스트 내포 기능을 이용하여 각 자리수의 세제곱을 구했다. 원하는 값을 찾기 위해 이분탐색을 이용한 탐색을 했다. 원하는 값이 나오지 않는다면 -1을 리턴했다.

---

3. 소스코드

#D3 5688 세제곱근을 찾아라.
arr = [i**3 for i in range(1000001)]
 
for t in range(1, int(input()) + 1):
    N = int(input())
    start, end = 0, 1000000
    answer = -1
    while start <= end:
        avg = (start+end)//2
        if arr[avg] == N:
            answer = avg
            break
        elif arr[avg] > N:
            end = avg - 1
        else :
            start = avg + 1
    print('#{} {}'.format(t, answer))