프로그래머스 최대공약수와 최소공배수 3진법 뒤집기 (99클럽 코딩테스트 32일차 TIL)

목표

백준과 프로그래머스를 번갈아 풀어보면서 천천히 문제에 접근하면서 어떤식으로 풀어야할지 감을 잡는 연습을 하는게 목표이다.

문제

내가 생각했을때 문제에서 원하는부분

두 수를 입력받아 두 수의 최대공약수, 최소공배수를 반환
예를 들어 3, 12 최대공약수는 3 최소공배수 12

내가 이 문제를 보고 생각해본 부분

유클리드 호제법을 사용하여 재귀적으로 최대공약수를 구한다.
최소공배수는 두 수의 곱을 최대공약수로 나누면 구해준다.

코드로 구현

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2]; 
        
        int gcd = gcd(n, m); // 최대 공약수
        int Icm = n * m / gcd; // 최소 공배수 = 두수의 곱 / 최대공약수
        
        answer[0] = gcd;
        answer[1] = Icm;
        
        System.out.println(answer);
        return answer;
    }
    
    // 유클리드 호제법
    public int gcd(int n, int m) {
        if(m == 0) {
            return n;
        } 
        return gcd(m, n%m);
    }
}

// 두 수를 입력받아 두 수의 최대공약수, 최소공배수를 반환
// 예를 들어 3, 12 최대공약수는 3 최소공배수 12

// 유클리드 호제법을 사용하여 재귀적으로 최대공약수를 구한다.
// 최소공배수는 두 수의 곱을 최대공약수로 나누면 구해준다.

시간복잡도 O(log(min(n, m)))
유클리드 호제법을 사용했기 때문에 재귀 호출의 깊이가 n과 m 중 작은 값의 비트 길이에 비례하게 된다.

장점
구현이 간단하다.
시간 복잡도가 빠르다.

단점
재귀 호출로 인해 스택이 커질 수 있다.
입력값에 따라 시간 복잡도 차이가 크다.

내가 생각했을때 문제에서 원하는부분

자연수 n이 매개변수로 주어진다.
n을 3진법 상에서 앞두로 뒤집은 후 이를 다시 10진법으로 표현한 수를 return

내가 이 문제를 보고 생각해본 부분

자연수 n을 3진법으로 변환
3진법 수를 뒤집기 
뒤집힌 3진법 수를 10진법으로 변환 

코드로 구현

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        // 1. 자연수 n을 3진법으로 변환하기
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            sb.append(n % 3);
            n /= 3;
        }

        // 2. 3진법 수를 뒤집기
        String reversedTernary = sb.toString();

        // 3. 뒤집힌 3진법 수를 10진법으로 변환하기
        int reversedDecimal = Integer.parseInt(reversedTernary, 3);

        // 4. 최종 결과 반환하기
        return reversedDecimal;
    }
}

// 자연수 n이 매개변수로 주어진다.
// n을 3진법 상에서 앞두로 뒤집은 후 이를 다시 10진법으로 표현한 수를 return

// 자연수 n을 3진법으로 변환
// 3진법 수를 뒤집기 
// 뒤집힌 3진법 수를 10진법으로 변환 

시간복잡도 O(log3(n))

장점
시간 복잡도가 O(log3(n))이므로, 입력값이 매우 큰 경우에도 상대적으로 빠른 실행 속도를 가질 수 있다.
이진법이나 십진법 변환에 비해 연산 횟수가 적어 효율적이다.

단점
입력값이 작은 경우에는 다른 방법에 비해 더 많은 연산을 수행하게 되어 더 많은 시간이 소요될 수 있다.
3진법 변환 및 뒤집기, 10진법 변환 등 여러 단계의 연산이 필요하므로 코드가 다소 복잡해질 수 있다.

마무리

최대공약수 최소공배수는 자주 볼 수 있는 문제인것같다. 가끔 심심하면 나오는것같다. 이번 문제를 통해서 재귀함수를 사용해서 문제를 해결해볼려고 노력했다.