[자바] 백준 3142 - 즐거운 삶을 위한 노력 (java)

목차

문제 : boj3142

 

 

필요 알고리즘

• 정수론, 소수 판정, 에라토스테네스의 체
  
  • 에라토스테네스의 체를 사용해 소수를 구한 후 소인수분해를 해서 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  어떤 수가 완전제곱수인지 우선 생각해보자.

내가 풀이를 위해 생각한 완전제곱수 판정은, 소인수 분해 후 각 소인수의 개수가 모두 짝수라면 완전제곱수가 가능하다는 점을 이용하는 것이었다.

 

  예를들어서 예제 입력 2를 생각해보자.

입력 : 2 -> 현재 소인수는 2만 존재한다. 2가 홀수개이므로 불가하다.

입력 : 3 -> 현재 2x3 이므로 소인수는 2가 1개, 3이 1개이다. 둘 다 홀수개이므로 불가하다.

입력 : 6 -> 2x2x3x3이 된다. 2와 3 모두 짝수개 존재하므로 완전제곱수가 가능하다.

입력 : 15 -> 2x2x3x3x3x5 이므로 마찬가지로 소인수 3과 5가 홀수개라 불가하다.

...

 

  이런 방식이다. 즉, 실제로 곱해줄 필욘 없고(즉 수의 범위가 64비트 int형의 범위를 넘어갈 일 없고), 매번 입력으로 들어온 숫자를 소인수분해 후, 각 소인수가 현재까지 몇 번 나왔는지만 확인하면 된다. 

 

  이걸 위해 처음 생각했던 방식은 '코드 1'과 같이 100만이하의 모든 소수를 구해둔 후, 순회하며 직접 나눠보는 방식이다.

이건 '코드 1'에 작성해두었다. 이걸로도 통과는 잘 되며, 일반적으로 생각할 수 있는 아이디어일 것 같다. '코드 2'는 코드 1로 푼 후 더 빠른 다른 고수분들 코드 보다가 괜찮은 테크닉을 발견해 다시 풀어본 코드이다. 좀 더 효율적인 방식으로, 미리 100만이하의 모든 정수에 대해 가장 작은 소인수를 구해두는 방식이다.  좀 더 자세한 설명은 '에라토스테네스의 체를 활용한 소인수분해' 에 적어두었다.

 

 

코드 1 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private List<Integer> getPn(int limit) {
        List<Integer> pn = new ArrayList<>();
        boolean[] isPn = new boolean[limit+1];
        int sqrtN = (int)Math.sqrt(limit);
        for (int i = 3; i <= sqrtN; i+=2) {
            if (isPn[i]) continue;
            int base = i+i;
            while (base <= limit) {
                isPn[base] = true;
                base+=i;
            }
        }
        pn.add(2);
        for (int i = 3; i <= limit; i+=2) {
            if (!isPn[i]) pn.add(i);
        }
        return pn;
    }

    public void solution() throws Exception {
        List<Integer> pn = getPn(1000000);
        Map<Integer, Integer> pnMap = new HashMap<>();
        for (int i = 0; i < pn.size(); i++) pnMap.put(pn.get(i), i);

        boolean[] arr = new boolean[pn.size()];
        int oddCnt = 0;

        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (n-->0) {
            int a = Integer.parseInt(br.readLine());
            int idx = 0;
            int curPn = pn.get(idx);
            while (curPn <= Math.sqrt(a)) {
                while (a % curPn == 0) {
                    a /= curPn;
                    if (arr[idx] = !arr[idx]) oddCnt++;
                    else oddCnt--;
                }
                curPn = pn.get(++idx);
            }
            if (pnMap.containsKey(a)) {
                idx = pnMap.get(a);
                if (arr[idx] = !arr[idx]) oddCnt++;
                else oddCnt--;
            }
            sb.append(oddCnt==0?"DA":"NE").append('\n');
        }
        System.out.print(sb);
    }
}

 

 

코드 2 (좀 더 효율적임) : github

ㅇimport java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private int[] getMinimumPn(int limit) {
        int[] arr = new int[limit+1];
        for (int i = 2; i <= limit; i++) {
            if (arr[i] != 0) continue;

            int base = i;
            while(base <= limit) {
                if (arr[base] == 0)
                    arr[base] = i;
                base += i;
            }
        }
        return arr;
    }

    public void solution() throws Exception {
        int[] minimumPn = getMinimumPn(1000000);

        boolean[] arr = new boolean[minimumPn.length];
        int oddCnt = 0;

        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (n-->0) {
            int a = Integer.parseInt(br.readLine());

            while (a!=1) {
                int pn = minimumPn[a];
                if (arr[pn] = !arr[pn]) oddCnt++;
                else oddCnt--;

                a/=pn;
            }
            sb.append(oddCnt==0?"DA":"NE").append('\n');
        }
        System.out.print(sb);
    }
}