[프로그래머스] 24 : 예상 대진표 | N개의 최소공배수

목차

▸ 예상 대진표
▸ N개의 최소공배수

---

💡 예상 대진표 : Lv.2

▼ 문제

출처: 프로그래머스 코딩테스트 연습 > 2017 팁스다운 > 예상 대진표

▼ 내 풀이

• 1 vs 2 -> 1번 대결, 3 vs 4 -> 2번 대결.. 이런식으로 대결의 번호로 접근하고자 했다.
• 대결의 번호를 어떻게 정해야할지 몰라 찾아보다가 다른 사람의 풀이를 참고했다.

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0;
        while(true){
            a = a/2 + a%2;
            b = b/2 + b%2;
            answer++;
            
            if(a==b){
                break;
            }
        }

        return answer;
    }
}

---

💡 N개의 최소공배수 : Lv.2

▼ 문제

출처: 프로그래머스 코딩테스트 연습 > 연습문제 > N개의 최소공배수

▼ 내 풀이

• 전달 받은 배열의 길이가 1인 경우와 2인 경우, 3이상인 경우로 나누어서 접근했다.
• 배열의 길이가 1인 경우는 배열의 수가 최소공배수이기 때문에 그대로 반환한다.
• 두 수의 최대공약수를 구하는 메서드를 만들었다.
• if-else if문을 활용하여 arr 배열의 길이가 1과 2인경우를 나누어 처리했다.
• 우선, arr 배열의 0번째, 1번째 수를 가지고 최대공약수와 최소 공배수를 구한다.
• 이렇게 구한 최소 공배수와 arr 배열의 2번째 수를 가지고 최대공약수와 최소 공배수를 구한다.
• 위의 과정을 반복하면 배열의 수들의 최소 공배수를 구할 수 있다.

class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        int gcd = 0;
        int lcm = 0;
        
        if(arr.length == 1){
            return arr[0];
        }else if(arr.length == 2){
            gcd = calculateGCD(arr[0], arr[1]);
            lcm = (arr[0]*arr[1])/gcd;
            return lcm;
        }
        gcd = calculateGCD(arr[0], arr[1]);
        lcm = (arr[0]*arr[1])/gcd;
        for(int i = 2; i < arr.length; i++){
            gcd = calculateGCD(lcm, arr[i]);
            lcm = (lcm * arr[i])/gcd;
        }
        return lcm;
    }
    public int calculateGCD(int num1, int num2){
        int gcd = 0;
        
        for(int i = 1; i <= num1 && i <= num2; i++){
            if(num1%i==0 && num2%i==0){
                gcd = i;
            }
        }
        return gcd;
    }
}

▼ 알게된 점

• 유클리드 호제법: 최소 공배수 = (a*b)/최대공약수
• 여러 개의 숫자들의 최소 공배수를 구할 때는 앞의 두 수부터 차례대로 구하면 된다.