[백준] 약수, 배수와 소수

서론

---

이번에는 약수, 배수와 소수 문제를 풀어보았다.

모두 브론즈 티어의 문제여서 어렵지 않게 해결할 수 있었던 것 같다.

---

5086 : 배수와 약수

---

문제

---

https://www.acmicpc.net/problem/5086

5086번: 배수와 약수

이 문제는 두 수를 받아 해당 두 수 사이의 관계가 배수인지 약수인지 둘 다 아닌지를 판별하는 문제이다.

---

해설

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (a == 0 && b == 0) {
                break;
            }

            if(a % b == 0){
                sb.append("multiple");
            }
            else if(b % a == 0){
                sb.append("factor");
            }
            else {
                sb.append("neither");
            }
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

간단하게, 무한루프를 만들고, 0,0이 들어오면 break를 통해 빠져나오도록 하였다.

또한, 앞, 뒤 수를 각각 뒤, 앞의 수로 나누어 나머지가 0이면 배수이거나, 약수 이므로 

조건문을 통해 검사한 후 StringBuilder에 추가하여 출력하도록 하였다.

문제에서 조건문을 다 줘서 매우 간단하게 구현만 하면 풀 수 있었던 문제였다!.

---

2501 : 약수 구하기

---

문제

---

https://www.acmicpc.net/problem/2501

2501번: 약수 구하기

이 문제는 주어진 수의 K번째 작은 약수가 존재하는지, 있다면 몇인지를 알아내는 문제이다.

---

해설

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++) {
            if (N % i == 0) {
                K--;
            }
            if (K == 0) {
                bw.write(String.valueOf(i));
                break;
            }
        }
        if(K > 0){
            bw.write(String.valueOf(0));
        }

        bw.flush();
        bw.close();
    }
}

먼저 N의 약수를 구하기 위해 1부터 N(자기 자신)까지의 반복문을 수행하며,

K번째 작은 약수를 구하는 문제이기 때문에 약수를 하나 찾을 때마다 K값을 하나씩 감소시킨다.
N을 i로 나눈 나머지가 0이면 약수이므로, K--로 감소시키다 보면, K==0이면 이 후의 약수가 더 존재하더라도

굳이 더 구할 필요가 없기 때문에 break를 통해 반복문을 탈출하게 됩니다.

그리고 만약 K가 0보다 크면, N의 K번째 약수는 존재하지 않는 것이기 때문에 이를 조건문을 통해 확인해주도록 합니다.

 

이 문제는 코드를 조금 더 깔끔하게  작성하려면 반복문을 아래와 같이 작성할 수 있다.

int cnt = 0;
int res = 0;

for (int i = 1; i <= N; i++) {
	if (N % i == 0) {
    	cnt++;
    }
    if (K == cnt) {
    	res = i;
        break;
    }
}
bw.write(String.valueOf(res));

이런식으로 작성하면 변수가 2개 추가되어 메모리를 조금 더 사용하게 될 것 같아서 사용하지 않았는데,

코드 가독성을 생각하면 위의 코드가 더 좋은 것 같다.

또한 조건문을 한번 더 수행하지 않아도 돼서 더 좋은 것 같기도 하다.

실제로 결과를 보면, 두 코드의 차이가 예상한 대로 결과에 나타난다.

변수를 추가하지 않은 첫번째 코드의 경우 메모리를 적게 사용했으며, 코드 길이가 조금 더 길고,

두번째 코드는 이와 반대이다.

 

이렇게 결과를 직접 확인해보니, 예상한대로 나오는 것 같아서 조금 뿌듯하당 ㅋㅋ

---

9506 : 약수들의 합

---

문제

---

 

https://www.acmicpc.net/problem/9506

9506번: 약수들의 합

이 수는 약수들의 합이 자기 자신과 같으면 완전수라고 하는데 완전수인지를 판별하는 문제이다.

---

해설

---

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while (true) {
            ArrayList<Integer> arrayList = new ArrayList<>();
            int n = Integer.parseInt(br.readLine());
            if (n == -1){
                break;
            }
            for (int i = 1; i < n; i++) {
                if (n % i == 0) {
                    arrayList.add(i);
                }
            }
            int sum = 0;
            StringBuilder sb = new StringBuilder();
            sb.append(n).append(" = ");
            for (int i = 0; i < arrayList.size(); i++) {
                sum += arrayList.get(i);
                sb.append(arrayList.get(i));
                if ((i+1) != arrayList.size()){
                    sb.append(" + ");
                }
            }
            if (sum != n) {
                sb = new StringBuilder();
                sb.append(n).append(" is NOT perfect.");
            }
            sb.append("\n");
            bw.write(sb.toString());
        }
        bw.flush();
        bw.close();
    }
}

이 문제는, 각 케이스별로, ArrayList를 선언하며, 해당 수의 모든 약수를 구하고 리스트에 저장한다.

그리고, 약수를 모두 구하면, 해당 약수들을 모두 더하여, 자기 자신과 같은지를 판별하고, 출력문을 생성한다.

만약 같다면, 만든 출력문을 그대로 사용하고, 완전수가 아니라면, 새로운 출력문을 만들게 된다.!

출력문을 깔끔하게 만들고 싶어서 고민했던 문제인 것 같다!.

---

1978 : 소수 찾기

---

문제

---

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

이 문제는 주어진 수들 중 소수의 개수를 구하는 문제이다.

---

해설

---

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int cnt = N;

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            if(num < 2){
                cnt--;
            }
            for (int j = 2; j < num; j++) {
                if(num % j == 0){
                    cnt--;
                    break;
                }
            }
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
    }
}

이 문제를 해결하기 위해 먼저 cnt라는 변수에 N을 대입하고 이를 소수의 개수로 사용한다.

각 케이스별로, 해당 수를 2 ~ 자기자신 - 1 의 반복문을 통해 나누어 떨어지는 수가 있는지 확인하며,
소수인지 판별하게 된다.

만약 소수가 아니라면 cnt--를 통해 전체 판별할 수에서 1을 빼고, 최종 결과에 cnt를 출력하게 된다.

또한, 만약 2 ~ 자기자신 - 1의 수로 나머지를 구해보는 과정에서 소수가 아니라고 판별되면,

약수 ~ 자기자신 - 1의 반복문을 수행하는 것은 위의 문제와 마찬가지로, 비효율적이기 때문에

break;를 통해 반복문을 탈출하도록 하였다!.

---

2581 : 소수

---

문제

---

https://www.acmicpc.net/problem/2581

2581번: 소수

이 문제는 M <= x <= N 인 x 중 소수인 것들의 합과, 해당 소수들 중 최소값을 구하는 문제이다.

이 문제는 예외케이스를 하나 빼먹어서 한번 틀렸었다ㅠㅠ.

---

해설

---

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        ArrayList<Integer> primes = new ArrayList<>();
        for (int i = M; i <= N ; i++) {
            boolean check = false;
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    check = true;
                    break;
                }
            }
            if (!check) {
                primes.add(i);
            }
        }
        int sum = 0;
        for (int i = 0; i < primes.size(); i++) {
            sum += primes.get(i);
        }
        StringBuilder sb = new StringBuilder();
        if(sum == 0){
            sb.append(-1);
        }
        else {
            sb.append(sum).append("\n").append(primes.get(0));
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

먼저 틀린 코드를 먼저 살펴보자.

해당 코드는 소수를 저장할 ArrayList를 선언하고 for M~N을 통해 반복문을 수행하며, 해당 수가 소수인지를 판단하여 check 변수에 해당 여부를 저장하고 이를 통해 소수라면 리스트에 저장하도록 한다.

그리고, 해당 리스트의 모든 값을 더하고, 해당 리스트의 idx = 0인 것이 최솟값이므로 이를 출력해준다.

이렇게만 놓고 보면, 어디가 잘못된 것인지 알아내기 어려울 것이다. (나만 그런가..?)

 

아무튼 이 코드의 문제점은 바로 1에 대한 예외처리를 하지 않은 것이다.

1이 소수가 아니기 때문에 2부터 나누어보고 했던 것인데, 1이 입력으로 들어온 경우를 확인하지 않았기 때문에,

틀렸습니다 라는 결과를 얻어서 매우 당황했다 ㅠㅠ.

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        ArrayList<Integer> primes = new ArrayList<>();
        for (int i = M; i <= N ; i++) {
            if(i <= 1){
                continue;
            }
            boolean check = false;
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    check = true;
                    break;
                }
            }
            if (!check) {
                primes.add(i);
            }
        }
        int sum = 0;
        for (int i = 0; i < primes.size(); i++) {
            sum += primes.get(i);
        }
        StringBuilder sb = new StringBuilder();
        if(sum == 0){
            sb.append(-1);
        }
        else {
            sb.append(sum).append("\n").append(primes.get(0));
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

그렇기 때문에 위의 if (i <= 1) continue; 구문을 추가하여, 1보다 작거나 같은 경우 해당 반복문을 넘어가도록 하였다!.

틀렸다는 결과를 받고, 뭐가 잘못되었는지도 사실 알아채질 못해서, 질문 게시판의 반례를 열심히 찾아보았다.

그런데, 대부분의 반례에서도 옳은 값을 출력해서 더 당황스러웠는데,

1 10의 케이스를 입력해보니 최소값이 1이 출력되는 것을 보고 알아차렸다!.

---

11653 : 소인수분해

---

문제

---

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

이 문제는 입력받은 수를 소인수분해하면 되는 아주 간단한 문제이다!.

---

해설

---

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int num = 2;

        while (N > 1) {
            if(N % num == 0){
                N /= num;
                sb.append(num).append("\n");
            }
            if(N % num != 0){
                num++;
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

간단하게, N을 2부터 점차 수를 키워가며 나누어보며, 나머지가 0인 경우 N /= num을 통해 N을 업데이트 해준다.

그리고, 만약 N /= num을 통해 업데이트 된 N이 또 다시 num으로 나누어 떨어진다면, num은 그대로 유지 시켜서 다시 나누어야 하기 때문에 조건문을 통해 num을 증가시킬지를 확인해주도록 한다.

예를 들어 N = 72일 경우 72 % 2 = 0이다. 그러면 72 /= 2 를 통해 N = 36이 되는데, 이때 num을 그냥 증가시켜버린다면,

실제 72의 소인수 분해인 2, 2, 2, 3, 3이라는 결과를 얻을 수 없을 것이기 때문이다!.

---

결론

---

이렇게 모든 문제를 풀어보았는데, 브론즈 단계여서 그런지 생각보다 간단하게 문제가 해결되었으며,

메모리, 시간 등을 고려하며 문제를 풀 생각을 하게 된 나 자신에 대한 칭찬을 하고 싶다. (๑˃́ꇴ˂̀๑)

예전에는 그냥 문제만 해결하면 메모리를 얼마를 쓰든, 시간이 얼마나 걸리든(물론, 시간 제한 안걸리는 선에서)

신경도 안썼는뎁... 많이 발전했다 나 자신! 앞으로도 화이팅 (੭˙ ˘ ˙)੭

---