[랜덤 마라톤] 짝 곱(9753)

1. 문제 풀이 아이디어

• 문제의 입력 값의 범위가 좁아서, 범위 내의 모든 소수들의 곱을 구한 후 검색하면 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        List<Integer> mulList = getMulList();
        int t = Integer.parseInt(bufferedReader.readLine());
        for (int i = 0; i < t; i++) {
            int k = Integer.parseInt(bufferedReader.readLine());
            stringBuilder.append(mulList.get(find(0, mulList.size(), k, mulList))).append('\n');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }

    private static List<Integer> getMulList() {
        List<Integer> prime = new ArrayList<>();
        Set<Integer> mulSet = new TreeSet<>();
        for (int i = 2; i < 50000; i++) {
            if (isPrime(i))
                prime.add(i);
        }
        for (int i = 0; i < prime.size() - 1; i++) {
            for (int j = i + 1; j < prime.size(); j++) {
                int mul = prime.get(i) * prime.get(j);
                if (mul <= 100001 && mul > 0)
                    mulSet.add(mul);
            }
        }
        return new ArrayList<>(mulSet);
    }

    private static boolean isPrime(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    private static int find(int s, int e, int k, List<Integer> list) {
        while(s<e){
            int mid=(s+e)/2;
            if(list.get(mid)>=k){
                e=mid;
            }else{
                s=mid+1;
            }
        }
        return s;
    }
}

3. 정리

• getMulList() 메서드
• prime리스트에 50000보다 작은 소수를 모두 저장한다.
• 소수들의 곱을 계산하고, 오버플로우를 고려하여 0보다 크고, 결과값의 범위인 100001 이하인 값만 mulSet에 저장한다.
• mulSet은 값의 중복을 방지하고 자동으로 정렬되도록 TreeSet을 사용한다.
• mulSet을 리스트로 변환하여 반환합니다.

• k를 입력받으면 find 메서드에서 이진 탐색을 통해 k보다 크거나 같은 값 중 가장 작은 값의 인덱스를 찾고, 그 인덱스를 사용하여 mulList에서 해당 값을 구해 출력한다.

4. 더 좋은 코드 리뷰

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int i, cnt;
        int testcase;
        for (testcase = 0; testcase < t; testcase++) {
            int k = sc.nextInt();
            while (true) {
                cnt = 0;
                int sq = (int) Math.sqrt(k);
                if (sq * sq != k) {
                    for (i = sq; i > 1; i--) {
                        if (k % i == 0) cnt++;
                    }
                }
                if (cnt != 1) k++;
                else break;
            }
            System.out.println(k);
        }
        sc.close();
    }
}

• k의 제곱근 값을 구하고 소수점 자리는 버린 후 sq에 저장한다.

• k가 완전 제곱수가 아니라면, sq보다 작은 약수의 개수를 cnt에 저장한다.

• cnt가 1이 아니면 k를 증가시키고, cnt가 1이면 k는 처음의 k보다 크거나 같은 수 중에서 가장 작은 두 소수의 곱이 된다.