Greedy Algorithm

 

---

< 문제 >

 

1. Activity Selection Problem : 수강신청할 때 한 사람이 최대한 많이 들을 수 있을 때의 수업명을 출력

// Activity selection problem

package greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class Activity {
    String name;
    int start;
    int end;

    public Activity(String name, int start, int end) {
        this.name = name;
        this.start = start;
        this.end = end;
    }
}

public class Greedy {
    public static void selectActivity(ArrayList<Activity> list) {
        Collections.sort(list, (x1,x2) -> x1.end - x2.end);

        int curTime = 0;
        ArrayList<Activity> result = new ArrayList<>();
        for (Activity item: list) {
            if (curTime <= item.start) {
                curTime = item.end;
                result.add(item);
            }
        }

        for (Activity item : result) {
            System.out.print(item.name + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ArrayList<Activity> list = new ArrayList<>();
        list.add(new Activity("A", 1, 5));
        list.add(new Activity("B", 4, 5));
        list.add(new Activity("C", 2, 3));
        list.add(new Activity("D", 4, 7));
        list.add(new Activity("E", 6, 10));
        selectActivity(list);
    }
}

- 출력

C B E

 

 

2. 거스름돈 구하기

// 거스름돈

package greedy;

import java.util.HashMap;
import java.util.Map;

public class changeProblem {
    public static void getChangeCoins(int receivedMoney, int price) {
        final int[] coins = {500,100,50,10,5,1};            // final: 수정할 수 없는 변수
        HashMap<Integer, Integer> result = new HashMap<>();

        int change = receivedMoney - price;
        int cnt = 0;            // 잔돈개수

        for (int i = 0; i < coins.length; i++) {
            if (change < coins[i]) {
                continue;
            }

            int q = change / coins[i];
            // 원래 가지고 있던 값(없다면 0)에서 q만큼 더함
            result.put(coins[i], result.getOrDefault(coins[i], 0) + q);

            change %= coins[i];
            cnt += q;
        }

        System.out.println("거스름돈 동전 개수: " + cnt);
        for (Map.Entry<Integer, Integer> cur : result.entrySet()) {
            System.out.println(cur.getKey() + ": " + cur.getValue());
        }
    }

    public static void main(String[] args) {
        getChangeCoins(1000, 100);
        getChangeCoins(1234, 500);
    }
}