[백준] 단계별로 풀어보기 > 기본 수학2 (Java)

+) 풀이 코드

https://github.com/jung0115/CodingTestPractice.git

GitHub - jung0115/CodingTestPractice: Practice Coding Test with Beakjoon, programmers, etc.

 

+) 백준에 Java 코드를 제출할 때는 class명을 Main으로 해주어야 오류가 발생하지 않는다.

 

1978번 - 2021.12.29.수

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int N; //입력 받을 수의 개수
        int[] input_num = new int[100];
        int cnt = 0; //소수의 개수

        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();

        for(int i = 0; i < N; i++) {
            input_num[i] = scan.nextInt();
        }

        scan.close();

        for(int i = 0; i < N; i++) {
            cnt += primeNumber(input_num[i]);
        }

        System.out.print(cnt);
    }
    static int primeNumber(int num){
        if(num == 1) return 0; //1은 소수가 아니다.
        for(int i = 2; i <= num/2; i++) { //소수인지 아닌지 판별
            if(num%i == 0) return 0; //소수가 아니면 0 반환
        }
        return 1;
    }
}

 

2581번 - 2021.12.29.수

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int M, N, sum = 0, min = -1;

        Scanner scan = new Scanner(System.in);
        M = scan.nextInt();
        N = scan.nextInt();
        scan.close();

        for(int num = M; num <= N; num++) {
            if(primeNumber(num)) { //num이 소수인 경우
                sum += num;
                if(min == -1) min = num; //num은 계속 증가하므로 처음 등장한 소수가 가장 최솟값이 된다.
            }
        }

        if(min == -1){
            System.out.println(min);
        }
        else {
            System.out.println(sum);
            System.out.println(min);
        }

    }
    static boolean primeNumber(int num){
        if(num == 1) return false; //1은 소수가 아니다.
        for(int i = 2; i <= num/2; i++) { //소수인지 아닌지 판별
            if(num%i == 0) return false; //소수가 아니면 false 반환
        }
        return true;
    }
}

 

11653번 - 2021.12.31.금

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int N;

        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        scan.close();

        for(int i = 2; i*i <= N; i++) {
            while((N%i) == 0) {
                N /= i;
                System.out.println(i);
            }
        }
        if(N != 1) System.out.println(N);
    }
}

처음에 나누는 값을 하나하나 소수인지 판단해서 나눠줬는데 그랬더니 시간초과가 됐다. 생각해보니 작은 수부터 나누면 당연히 소인수로만 나눌 수 밖에 없었다... 그래서 소인수 판단하는 부분 없이 바로 나눠주었는데, 그래도 한 문제 빼고는 다 시간초과가 걸렸다. 최대한 반복횟수를 줄일 수 있도록 break로 빠져나가는 조건들을 달아주었지만 별 효과 없었다. 결국 구글에 검색... for문 반복 조건을 나는 i<=N/2으로 하고 애초에 N이 나눠지는 것이 아니라 새로운 변수를 만들어서 그 값이 나눠지게 했기 때문에 반복이 더 많이 돌아갔던 거였다. 새로운 변수를 두지 않고 N을 바로 나눠지게 하고, N값의 변화에 따라 i<=N의 제곱근을 반복 조건으로 두니 문제 없이 풀이가 통과되었다.

(시간초과를 상관하지 않으면 처음의 방법도 원하는 값을 얻을 수는 있지만 더 효율적인 코드를 짜는 것이 중요할 것 같다.)

 

1929번 - 2021.01.03.월

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int M, N;

        Scanner scan = new Scanner(System.in);
        M = scan.nextInt();
        N = scan.nextInt();
        scan.close();

        for(int i = M; i <= N; i++){
            if(checkPrimeNumber(i)){ //i가 소수인 경우
                System.out.println(i); //출력
            }
        }
    }
    static boolean checkPrimeNumber(int num) { //소수 판단 함수
        if(num == 1) return false;
        for(int i = 2; i*i <= num; i++) {
            if(num%i == 0) return false; //소수가 아닌 경우
        }
        return true; //소수인 경우
    }
}

 

4948번 - 2022.01.04.화

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int[] checkPrime = new int[246913];

        //1부터 123456*2, 즉 246912까지 각각 소수인지 아닌지 판단하여 배열에 저장
        for(int i = 1; i <= 246912; i++){
            checkPrime[i] = checkPrimeNumber(i);
        }

        Scanner scan = new Scanner(System.in);
        while(true) {
            int n, cnt = 0;
            n = scan.nextInt();
            if(n == 0) break;
            for(int i = n+1; i <= 2*n; i++) cnt += checkPrime[i]; //n보다 크고 2n보다 작거나 같은 소수의 개수 계산
            System.out.println(cnt);
        }
        scan.close();
    }
    static int checkPrimeNumber(int num) { //소수 판단 함수
        if(num == 1) return 0;
        for(int i = 2; i*i <= num; i++) {
            if(num%i == 0) return 0; //소수가 아닌 경우
        }
        return 1; //소수인 경우
    }
}

 

9020번 - 2022.01.04.화

import java.util.Scanner;
public class Main {
    static boolean[] checkPrime = new boolean[10001];
    public static void main(String[] args) {
        //1부터 10000까지의 수가 각각 소수인지 판단하여 배열에 저장
        for(int i = 1; i <= 10000; i++) {
            checkPrime[i] = checkPrimeNumber(i);
        }

        int T;
        Scanner scan = new Scanner(System.in);
        T = scan.nextInt();
        for(int i = 0; i < T; i++) {
            int n = scan.nextInt();
            Goldbach(n);
        }
        scan.close();
    }
    static boolean checkPrimeNumber(int num) { //소수 판단 함수
        if(num == 1) return false;
        for(int i = 2; i*i <= num; i++) {
            if(num%i == 0) return false; //소수가 아닌 경우
        }
        return true; //소수인 경우
    }
    static void Goldbach(int num) { //num에 대한 골드바흐 파티션을 찾아서 출력하는 함수
        int max, min, sum;
        max = maxPrime(num/2);
        min = minPrime(num/2);
        while(true) {
            sum = max + min;
            if(sum == num) break; //num에 대한 골드바흐 파티션을 찾은 경우
            else if(sum > num) min = minPrime(min-1);
            else max = maxPrime(max+1);
        }
        System.out.println(min + " " + max);
    }
    static int maxPrime(int num) { //num보다 큰 수 중 가장 작은 소수
        for(int i = num; ; i++)
            if(checkPrime[i]) return i;
    }
    static int minPrime(int num) { //num보다 작은 수 중 가장 작은 소수
        for(int i = num; ; i--)
            if(checkPrime[i]) return i;
    }
}

 

1085번 - 2022.01.04.화

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int x, y, w, h;
        Scanner scan = new Scanner(System.in);
        x = scan.nextInt();
        y = scan.nextInt();
        w = scan.nextInt();
        h = scan.nextInt();
        scan.close();

        int[] len = new int[4];
        len[0] = x;
        len[1] = y;
        len[2] = w-x;
        len[3] = h-y;

        int min = len[0];
        for(int i = 1; i < 4; i++) {
            if(len[i] < min) min = len[i];
        }

        System.out.println(min);
    }
}

 

3009번 - 2022.01.08.토

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int[][] square = new int[3][2];
        
        Scanner scan = new Scanner(System.in);
        for(int i = 0; i < 3; i++){
            square[i][0] = scan.nextInt();
            square[i][1] = scan.nextInt();
        }
        scan.close();

        int x, y;
        x = different(square[0][0], square[1][0], square[2][0]);
        y = different(square[0][1], square[1][1], square[2][1]);

        System.out.println(x + " " + y);
    }
    static int different(int a, int b, int c) { //a, b, c 중 혼자 다른 수를 반환
        if(a == b) return c;
        if(a == c) return b;
        return a;
    }
}

 

4153번 - 2022.01.08.토

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int[] len = new int[3];
        Scanner scan = new Scanner(System.in);
        while(true) {
            len[0] = scan.nextInt();
            len[1] = scan.nextInt();
            len[2] = scan.nextInt();
            if(len[0] == 0) break;
            boolean check;
            check = checkTriangle(len);
            if(check) System.out.println("right");
            else System.out.println("wrong");
        }
        scan.close();
    }
    static boolean checkTriangle(int[] len) {
        //최대값 팀색
        int max = 0;
        if(len[max] < len[1]) max = 1;
        if(len[max] < len[2]) max = 2;
        
        int square1, square2;
        square1 = len[max]*len[max];
        len[max] = 0;
        square2 = len[0]*len[0] + len[1]*len[1] + len[2]*len[2];

        if(square1 == square2) return true;
        return false;
    }
}

 

3053번 - 2022.01.09.일

import java.util.Scanner;
import java.lang.Math;
public class Main {
    public static void main(String[] args) {
        int R;
        Scanner scan = new Scanner(System.in);
        R = scan.nextInt();
        scan.close();

        double Euclidean, Taxi;
        Euclidean = R*R*Math.PI;
        Taxi = R*R*2;

        System.out.println(Euclidean);
        System.out.println(Taxi);
    }
}

 

1002번 - 2022.01.09.일

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int T;
        Scanner scan = new Scanner(System.in);
        T = scan.nextInt();
        for(int i = 0; i < T; i++) {
            int x1, x2, y1, y2, r1, r2;
            x1 = scan.nextInt(); y1 = scan.nextInt(); r1 = scan.nextInt();
            x2 = scan.nextInt(); y2 = scan.nextInt(); r2 = scan.nextInt();
            
            int cnt;
            cnt = checkSpace(x1, y1, r1, x2, y2, r2);
            System.out.println(cnt);
        }
        scan.close();
    }
    static int checkSpace(int x1, int y1, int r1, int x2, int y2, int r2) {
        if(x1 == x2 && y1 == y2 && r1 == r2) return -1;

        int len, rSum, rSub;
        //len: 조규현과 백승환의 거리의 제곱
        //rSum: 조규현, 백승환 각각 류재명과의 거리를 합한 값의 제곱
        //rSub: 조규현, 백승환 각각 류재명과의 거리를 뺀 값의 제곱
        len = (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
        rSum = (r1 + r2)*(r1 + r2);
        rSub = (r1 - r2)*(r1 - r2);

        if(len > rSum || len < rSub) return 0;
        if(len == rSum || len == rSub) return 1;
        return 2;
    }
}

이 경우는 류재명의 위치가 될 수 있는 좌표의 개수가 각각 0, 1, 2, 무한대인 경우의 수를 고려해서 계산하면 되는 문제다. (원의 방정식으로 생각) 처음에 0인 경우 중에 원 하나가 나머지 원 안에 들어가지만 내접하지 않는 경우를 제대로 고려하지 않고, 1인 경우 중에서 내접하는 경우를 생각하지 않고 문제를 풀어서 50%만 맞다고 나왔었다. 이후 그 부분을 수정하여 다시 코드를 작성하였다.