[SW Expert] 5688. 세제곱근을 찾아라

생각

Github - https://github.com/hellojdh/Code/blob/master/src/swexpert/d3/Q5688.java

주어진 수 N의 세제곱근이 있는지 구하여라. 있다면 그 수를 아니라면 -1을 출력한다.

처음 생각

N이 10^18승 까지 주어지므로 무지무지 큰 숫자이다. 따라서 BigInteger를 이용해서 큰 수를 처리해 주었다.

다음 생각

일일히 세제곱근이 존재하나 판단해 주었더니 시간 초과를 얻었다.

▶ 에라토스테네스의 체 처럼 10^18승 이므로 10^6승 까지의 세 제곱을 미리 구해놓고 가능한지를 판단하는것으로 바꾸었다.

다다음 생각

10^6승 까지의 세제곱 수를 미리 구해놓고 판단을 하기 위해서 HashMap<String,Integer>로 Key값으로는 들어오는 값, Value로는 세제곱이 가능한 수를 넣어주었다.

▶ 일단 생각으로는 시간 복잡도가 O(N)이라고 생각되지만 String 값을 다루고, BigInteger의 사용으로 속도는 빠르지 않다.

방안

1) 큰 값을 다룰 수있는 다른 방안을 한 번 알아봐야겠다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

package swexpert.d3;   import java.math.BigInteger; import java.util.HashMap; import java.util.Scanner;   public class Q5688 {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         StringBuilder sb = new StringBuilder();         solve();         int tc = sc.nextInt();         for(int i=1;i<=tc;i++) {             sb.append("#"+i+" ");             String t = sc.next();             if(map.containsKey(t))                 sb.append(map.get(t)+"\n");             else sb.append("-1\n");         }         System.out.print(sb);     }          static HashMap<String,Integer> map = new HashMap<>();     private static void solve() {         // 10^18이 최대이므로 10^6 승까지의 세 제곱근을 구해준다.         for(int i=1;i<1_000_001;i++) {             BigInteger big = new BigInteger(i+"");             map.put(big.pow(3).toString(), i);         }     } }   Colored by Color Scripter

cs