2022.09.25 프로그래머스 알고리즘 공부

(Greedy) 구명보트

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people); // 오름차순으로 몸무게를 정렬
        
        int index = 0;
        
        // 가장 무거운 사람부터 시작
        // 가장 무거운사람+가벼운사람 -> limit을 넘지 않으면 index를 높혀서 
        // 가벼운 사람도 보트를 탄 걸로 가정
        // 무게가 오버되면 index를 높이지 않고 answer만 높혀서 보트만 카운트
        for (int i=people.length - 1; i>=index; i--) {
            if (people[i] + people[index] <= limit) {
                index++;
                answer++;
            } else {
                answer++;
            }
            
        }
        
        return answer;
    }
}

 

N개의 최소공배수

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0];
        // 첫번째 수와 그 다음수의 최소공배수를 구하고
        // 그 최소공배수와 그 다음수의 최소공배수 구하기
        
        for (int i=0; i<arr.length; i++) {
            answer = lcm(answer, arr[i]);
        }
        
        return answer;
    }
    
    //최대공약수
    static int gcd(int a, int b) {
        if (a%b == 0) {
            return b;
        }
        return gcd(b, a%b);
    }
    
    //최소공배수
    static int lcm(int a, int b) {
        return a*b / gcd(a,b);
    }
    
}

 

예상대진표

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;
    }
}