문제

[코플릿 - 빼빼로데이]

---

처음 작성한 코드

public class Main {
    public static ArrayList<Integer[]> divideChocolateStick(int M, int N) {
        ArrayList<Integer[]> result = new ArrayList<>();
        // 최대 공약수 구하기
        int GCD = gcd(M, N);
        // 공약수인 경우는 배열에 추가
        for (int i = 1; i <= GCD; i++) {
            if (M % i == 0 && N % i == 0) {
                Integer[] array = new Integer[]{i, M / i, N / i};
                result.add(array);
            }
        }
        return result;
    }

    // 유클리드 호제법
    public static int gcd(int M, int N) {
        if (M % N == 0) return N;
        return gcd(N, M % N);
    }
}

M과 N이 모두 나누어 떨어지는 값(= 공약수)과, 그때의 M, N의 몫들을 구해야한다.
M, N의 공약수는 최대 공약수보다 작으면서 M, N이 모두 나누어 떨어지는 값이다.

1. 유클리드 호제법을 사용하여, 최대 공약수 구하기
2. for문을 돌려, 공약수 찾기

---

시간 복잡도

전체 시간복잡도는 O(n)의 시간복잡도를 갖는다.

1. 최대 공약수를 찾는 gcd()의 시간 복잡도는 O(n)이다.

2. 이후에 for문을 도는 코드의 시간 복잡도도 O(n)이다.
   이때 실제 n은 M, N의 최대공약수이다. n은 입력된 M, N에 따라 다르지만, 빅오는 가장 최악의 경우를 고려하기 때문에 O(n)이라고 표현한다.

해서 O(n) + O(n) = O(n)이 된다.

for문에서 최대 공약수보다 작으면서, 공약수가 아닌 값들까지도 거쳐가야 하므로 효율성이 떨어진다.

---

시간 복잡도를 향상시킨 코드

생각해보면 우리가 구하려는 공약수는 결국 최대 공약수의 약수이다.

예를 들어, 최대 공약수가 36이면 공약수는 1, 2, 3, 4, 6, 9, 12, 18, 36이다.
첫번째 코드는 for문을 36번 돌게 되는데, 이는 비효율적이다.
어떤 수(N)의 약수는 제곱근을 제외하고는 짝이 지어져 있기 때문에 sqrt(N)까지만 for문을 돌면 된다.

36의 제곱근인 6까지만 for문을 돌고, 그때의 약수인 1, 2, 3, 4, 6을 left라고 하고 left의 짝을 right라고 하자.

left와 right가 존재할 때의 경우를 arraylist에 추가해주면 된다.
하지만 문제에서 원하는 정렬 조건을 만족하지 않기 때문에 마지막에 index = 0을 기준으로 오름차순 정렬을 해준다.

public class Solution {
    public static ArrayList<Integer[]> divideChocolateStick(int M, int N) {
        int GCD = gcd(M, N); // 최대 공약수 구하기
        ArrayList<Integer[]> result = new ArrayList<>();
    	
        for (int left = 1; left <= Math.sqrt(GCD); left++) {
            if (GCD % left == 0) { // 공약수인 경우
                result.add(new Integer[]{left, M / left, N / left});
                if (left < Math.sqrt(GCD)) {// left와 쌍인 공약수도 추가해줌
                    int right = GCD / left;
                    result.add(new Integer[]{right, M / right, N / right});
                }
            }
        }
        // 순서를 정렬
        Collections.sort(result, new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                return o1[0].compareTo(o2[0]);
            }
        });
        return result;
    }

    public static int gcd(int a, int b) {
        if (a % b == 0) return b;
        return gcd(b, a % b);
    }
}

시간 복잡도

두 번째 코드를 짰을 때, 오히려 정렬 때문에 시간 복잡도가 더 안 좋을 수도 있지 않을까? 라고 생각했다.
하지만 첫 번째 코드에 비해 for문도 훨씬 덜 돌고, 정렬도 공약수 몇 개에만 실행되기 때문에 첫 번째 코드에 비해 더 효율적이라고 볼 수 있다.

이 전체 코드의 시간 복잡도를 빅오로 표현해보면, O(n)이다.

1. 최대 공약수를 찾는 gcd()의 시간 복잡도는 O(n)이다.

2. for문을 도는 코드의 시간 복잡도도 O(n)이다.
   이때 실제 n은 sqrt(GCD)이다. n은 입력된 M, N에 따라 다르지만, 빅오는 가장 최악의 경우를 고려하기 때문에 O(n)이라고 표현한다.

3. 정렬은 앞에서 진행된 반복의 몇 가지 요소만 실행하기 때문에, 실제로 비교되는 크기가 달라서 시간 복잡도에 고려하지 않는다!

   원래 Collections.sort()의 시간 복잡도는 O(N log N)이다.