회의실 배정 문제

그리디 알고리즘

시간복잡도 O(nlogn)(정렬시간)

class Solution {
   public static int maxMeetings(int[][] meetings) {
       Arrays.sort(meetings, (a, b) -> {
           return a[1] - b[1];
       });
       
       int count = 1;  
       int lastEndTime = meetings[0][1];
      
       for (int i = 1; i < meetings.length; i++) {
           if (meetings[i][0] >= lastEndTime) {
               count++;
               lastEndTime = meetings[i][1];
           }
       }
       return count;
   }

   public static void main(String[] args) {
       // 테스트용 회의 배열 생성
       int[][] meetings = {
           {1, 4},  // 1번팀
           {3, 5},  // 2번팀
           {0, 6},  // 3번팀
           {5, 7},  // 4번팀
           {3, 8},  // 5번팀
           {5, 9},  // 6번팀
           {6, 10}, // 7번팀
           {8, 11}  // 8번팀
       };
       
       int maxCount = maxMeetings(meetings);
       System.out.println("최대 진행 가능한 회의 수: " + maxCount);
   }
}

동전 거스름돈 문제

그리디 알고리즘

시간 복잡도 O(n)

import java.util.*;

public class Solution {
    public static int coinChange(int[] coins, int target) {
        Arrays.sort(coins);

        int remainingAmount = target;
        int coinCount = 0;

        for (int i=coins.length-1; i>=0; i--){
            coinCount += remainingAmount / coins[i];
            remainingAmount %= coins[i]; 
        }
        return coinCount;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] coins = {500, 100, 50, 10};

        int target = scanner.nextInt();

        System.out.println(coinChange(coins, target));
    }
}