[수학] 백준 5618 공약수

5618번: 공약수

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

 

# 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        // N
        long n = Long.parseLong(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        if (n == 2) {
            long A = Long.parseLong(st.nextToken());
            long B = Long.parseLong(st.nextToken());
            // 두 수 중 작은 수까지만 반복하는 반복문
            for (long i = 1; i <= Math.min(A, B); i++) {
                if (A % i == 0 && B % i == 0) {
                    System.out.println(i);
                }
            }
        } else {
            long A = Long.parseLong(st.nextToken());
            long B = Long.parseLong(st.nextToken());
            long C = Long.parseLong(st.nextToken());
            // 세 수 중 작은 수까지만 반복하는 반복문
            for (long i = 1; i <= Math.min(A, Math.min(B, C)); i++) {
                if (A % i == 0 && B % i == 0 && C % i == 0) {
                    System.out.println(i);
                }
            }
        }
    }
}

• 공약수의 정의 그대로 간단하게 풀 수 있는 문제였다. (;;;)

 

위의 GOAT한 코드는 아래 블로그를 참고했다.

[백준/BOJ] 5618번 : 공약수 (JAVA / 자바)

 

 

아래는 아직도 왜 틀렸는지 모르는 댕복잡하게 생각해서 손해본 내 코드이다.

예시 입출력은 모두 맞게 나오는데 틀린 이유를 모르겠다 ... ಠ_ಠ

예상하기로는 너무 비효율적으로 코드를 짠 탓에 수가 커지게 되면 타임아웃이 발생하는 것 같다.

앞으로는 효율적이고 간결한 코드를 짜는 사람이 되어야지 .......

효간코짜

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

public class Main {
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N
        long n = Long.parseLong(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        if (n == 2) {
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            commonDivisor2(a, b);
        } else if (n == 3) {
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            long c = Long.parseLong(st.nextToken());
            commonDivisor3(a, b, c);
        }

        br.close();
    }

    // n == 2 일 때 공약수를 구하는 메소드
    public static void commonDivisor2(long a, long b) {
        LinkedList<Long> listA = getDivisorList(a);
        LinkedList<Long> listB = getDivisorList(b);

        LinkedList<Long> answer = new LinkedList<>();
        while (!(listA.isEmpty() || listB.isEmpty())) {
            if (listA.getFirst().equals(listB.getFirst())) {
                // a와 b의 공약수를 찾으면 answer에 추가하고 제거
                answer.add(listA.removeFirst());
                listB.removeFirst();
            } else if (listA.getFirst() < listB.getFirst()) {
                // a의 약수가 b의 약수보다 작으면 공약수가 아니므로 제거
                // (각 약수 리스트는 getDivisorList()를 거치며 정렬된 상태이기 때문)
                listA.removeFirst();
            } else {
                listB.removeFirst();
            }
        }

        // 출력
        for (Long ele : answer) {
            sb.append(ele).append("\n");
        }
        System.out.println(sb);
    }

    // n == 3 일 때 공약수를 구하는 메소드
    public static void commonDivisor3(long a, long b, long c) {
        LinkedList<Long> listA = getDivisorList(a);
        LinkedList<Long> listB = getDivisorList(b);
        LinkedList<Long> listC = getDivisorList(c);

        LinkedList<Long> answer = new LinkedList<>();
        while (!(listA.isEmpty() || listB.isEmpty() || listC.isEmpty())) {
            if (listA.getFirst().equals(listB.getFirst()) && listA.getFirst().equals(listC.getFirst())) {
                // a, b, c의 공약수를 찾으면 answer에 추가하고 제거
                answer.add(listA.removeFirst());
                listB.removeFirst();
                listC.removeFirst();
            } else {
                // 세 약수 리스트의 첫 번째 값 중 가장 작은 값 제거
                String min = "a";
                if ((listB.getFirst() < listA.getFirst()) && (listB.getFirst() < listC.getFirst())) {
                    min = "b";
                }
                if ((listC.getFirst() < listA.getFirst()) && (listC.getFirst() < listB.getFirst())) {
                    min = "c";
                }

                switch (min) {
                    case "a":
                        listA.removeFirst();
                        break;
                    case "b":
                        listB.removeFirst();
                        break;
                    case "c":
                        listC.removeFirst();
                        break;
                }
            }
        }

        // 출력
        for (Long ele : answer) {
            sb.append(ele).append("\n");
        }
        System.out.println(sb);
    }

    // x의 약수를 리스트로 리턴하는 함수
    public static LinkedList<Long> getDivisorList(long x) {
        // 약수를 담을 리스트 result
        LinkedList<Long> result = new LinkedList<>();
        for (long i = 1; i <= x; i++) {
            // x를 i로 나누었을 때 나누어떨어지면 result에 담기
            if (x % i == 0) {
                result.add(i);
            }
        }
        return result;
    }
}