프로그래머스, 백준 소수판정 문제들

문제1

프로그래머스

풀이1

1. n개 중에서 3개를 순서에 상관없이 뽑는다.
2. 해당 개수의 합(s)이 소수인지 판정하고 소수라면 ans++;
   • 소수 판정: (소수는 1과 자신 만을 약수로 가지고 있는 수)
   • Number.isInteger(Math.sqrt(s))가 true라면 소수가 아님 (제곱근의 약수를 가지고 있다는 뜻)
   • 2~Math.sqrt(s)를 순회하며 s%i == 0 이면 소수가 아님(이외의 약수가 존재한다는 뜻)

코드1(JS)

let arr, len, ans=0;
function solution(nums) {
    arr = nums;
    len = nums.length;
    comb(0, 0, 0); // 조합: n(len) 개수 중 3개 뽑기
    return ans;
}
function comb(depth, start, sum){
    if(depth == 3){
        // 소수 판정
        if(isSosu(sum)) ans++;
        return;
    }
    for(let i = start ; i < len ; i ++){
        comb(depth+1, i+1, sum+arr[i]);
    }
}
function isSosu(n){
    let tmp = Math.sqrt(n);
    if(Number.isInteger(tmp)) return false;
    for(let i = 2 ; i < tmp ; i ++){
        if(n%i == 0) return false;
    }
    console.log(n);
    return true;
}

문제2

1929번: 소수 구하기

• M 이상 N 이하의 소수를 모두 출력

풀이2

1. 에라토스테네스의 체 알고리즘을 활용하여, 소수를 먼저 구함
2. M ~ N 까지 순회하며 prime[i]가 false라면 출력

코드2(Java)

import java.util.*;

public class Main {
    public static boolean[] prime;
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        prime = new boolean[N + 1];
        getPrime(); // 소수 구하기

        StringBuilder sb = new StringBuilder();
        for(int i = M; i <= N; i++)
            if(!prime[i]) sb.append(i).append('\n'); // false = 소수 

        System.out.println(sb);
    }


    // 에라토스테네스의 체 알고리즘
    public static void getPrime() {
        // true = 소수아님 , false = 소수 
        prime[0] = prime[1] = true;

        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            if(prime[i]) continue;
            for(int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

문제3

1644번: 소수의 연속합

• 소수의 연속 합이 주어진 N이 되는 케이스의 총 개수 구하는 문제

풀이3

1. 에라토스테네스의 체 알고리즘을 통해 소수를 구한다.
2. 소수에 해당하는 수만 list에 넣어준다.
3. 투 포인터 알고리즘을 이용해 list를 순회하며 sum과 N의 값이 같으면 cnt를 1 증가한다.
   • 투 포인터 알고리즘
     • left, right, sum, cnt를 0으로 초기화
     • case1) sum이 N보다 크면, sum -= list.get(left++);
     • case2) list의 size == right라면 break;
     • case3) 이외의 경우, sum += list.get(right++);
     • 또한, N == sum이라면, cnt++;

코드3(Java)

import java.io.*;
import java.util.*;

public class Main {

    static List<Integer> list;
    static boolean[] isPrime;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        isPrime = new boolean[N+1];
        list = new ArrayList<>();

        eratos();

        for (int i = 1; i <=N ; i++)
            if(!isPrime[i]) list.add(i);

        int s, e, sum, cnt;
        s = e = sum = cnt = 0;
        while (true){
            if(sum >= N) sum -= list.get(s++);
            else if(e == list.size()) break;
            else sum += list.get(e++);

            if(N==sum) cnt++;
        }

        System.out.println(cnt);
    }

    private static void eratos() {
        isPrime[0] = isPrime[1] = true;
        int sqrtNum = (int)(Math.sqrt(N));
        for(int i = 2 ; i <= sqrtNum ; i ++) {
            if(!isPrime[i]) {
                for(int j=i*i; j<=N; j+=i)
                    isPrime[j]=true;      
            }
        }
    }
}

문제4

1963번: 소수 경로

• 시작 수(s)에서 종료 수(e) 까지 변환이 가능할 경우 최소 몇 번으로 바꿀 수 있는지 구하는 문제
• 변환 과정에서 수는 항상 소수가 보장되어야 함
• 시작수와 종료 수는 4자리로 주어지며, 변환 과정의 수 또한 4자리 이어야 함
• 1000 ~ 9999 사이의 수에 대해서만 판단

풀이4

• 에라토스테네스의 체 알고리즘을 활용하여 소수인지 아닌지 먼저 구한다.
• bfs 탐색을 통해, 2중 for문 탐색을 진행한다.
  • 첫번째 자리 ~ 4번째 자리 순회, 자리마다 올 수 있는 수(0~9) 순회를 진행
  • 첫번째 자리가 0이며 바꿀 수가 0이면 continue
  • 수 변환은 StringBuilder의 setCharAt 메서드를 활용하여 변환 진행
    • setCharAt(바꿀 인덱스, 바꿀 수)

코드4(Java)

import java.io.*;
import java.util.*;

public class Main {
    static int start, end;
    static int[] cnt; // 현재까지의 바꾼 횟수가 담겨있는 배열
    static boolean[] v, isPrime;

    static class Node {
        int node;
        int time;

        public Node(int node, int time) {
            this.node = node;
            this.time = time;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        isPrime = new boolean[10000]; // false 값이 소수
        isPrimeFunc();

        int T = Integer.parseInt(st.nextToken());
        while (T-- > 0) {
            cnt = new int[10000];
            v = new boolean[10000];
            st = new StringTokenizer(br.readLine());

            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());

            bfs();

            System.out.println(cnt[end]);
        }
    }

    private static void isPrimeFunc() {
        isPrime[0] = isPrime[1] = true;
        for (int i = 1001; i <= 9999; i++) {
            int sqrtNum = (int)Math.sqrt(i);
            for (int j = 2; j <= sqrtNum; j++) {
                for(int k = j*j ; k <= i ; k += j){
                    isPrime[k] = true;
                }
            }
        }
    }

    private static void bfs() {
        Queue<Integer> q = new ArrayDeque<>();
        v[start] = true;
        q.offer(start);

        while (!q.isEmpty()) {
            int curr = q.poll();

            for (int d = 0; d < 4; d++) {
                for (int i = 0; i < 10; i++) {
                    if(d==0 && i==0) continue;

                    int nr = change(curr, d, i);

                    if(!isPrime[nr] && !v[nr]){
                        v[nr] = true;
                        cnt[nr] = cnt[curr] + 1;
                        q.offer(nr);
                    }
                }
            }
        }
    }
    // 특정 자릿수를 들어온 값으로 바꾸기 위한 함수
    public static int change(int num, int i, int j) {
        StringBuilder sb = new StringBuilder(String.valueOf(num)); // int를 stringBuilder로 바꿈
        sb.setCharAt(i, (char) (j + '0')); //(인덱스, 바꿀문자)  (char) (v + '0') = int v를 문자 v로 만듬
        return Integer.parseInt(sb.toString()); // 그냥 sb 하면 안되는 이유는 괄호안에 타입이 string이기 때문
    }
}