[프로그래머스] Greedy

그리디 알고리즘은, 탐욕적 알고리즘으로 불리며 순간에서 가장 최선의 선택을 하면 결과적으로 가장 효율적인 알고리즘이다.

 

기지국 설치

- 큐로 풀면 시간 초과 나옴

public int solution(int n, int[] stations, int w) {
    int answer = 0;
    int index = 0;
    int position = 1;
    while (position <= n) {
        // 기지국 전파 범위에 들어오면, 기지국 전파 범위 맨 우측에서 시작함
        if (index < stations.length && stations[index] - w <= position) {
            position = stations[index] + w + 1;
            index += 1;
            // 그렇지 않을 경우 기지국을 정석대로 (그리디로 설치)
        } else {
            answer += 1;
            position += w * 2 + 1;

        }
    }

    return answer;
}

자전거 공장

- 개인적으로 이게 더 어려운 거 같다.

- 핵심은 재고를 체크하면서 남은 건 이월해야 하는 로직을 구현한다. rest 변수 활용

    private static int solution(int[][] cost, int[][] order) {
        int answer = 0;

        // 가장 큰 월
        int maxMonth = 0;
        for (int[] o : order) maxMonth = Math.max(maxMonth, o[0]);

        // 정렬하고 만들어야 하는 자전거 개수 구함
        int[] monthlyOrder = new int[maxMonth];
        int need = 0;
        int made = 0;
        for (int[] o : order) {
            monthlyOrder[o[0] - 1] += o[1];
            need += o[1];
        }

        String result = Arrays.stream(monthlyOrder)
                .mapToObj(String::valueOf)
                .collect(Collectors.joining(", "));

        System.out.println(result);

        // 가격 범위로 루프 순회
        for (int i = 0; i < cost.length - 1; i++) {
            if (need == 0 || made >= need) break;

            int price = cost[i][1]; // 가격
            int limit = cost[i + 1][0] - cost[i][0]; // 재고 제한
            int rest = 0;

            // 주문이 0원이면 재고를 쌓고
            // 주문이 있을 경우, 배송을 함
            // 배송을 하고 남은 주문은 이월되며, 배송만큼 주문이 차감됨
            // 다시 가격 범위 루프 돌면서 answer에 더해짐
            for (int j = 0; j < maxMonth; j++) {
                if (need == 0 || made >= need) break;

                int making = Math.min(limit, need - made);
                answer += making * price;
                made += making;

                if (monthlyOrder[j] == 0) continue;
                need -= monthlyOrder[j];

                int delivery = Math.min(made, monthlyOrder[j]);
                made -= delivery;
                monthlyOrder[j] -= delivery;
                rest += monthlyOrder[j];
            }

            need = rest;
            made = 0;
        }

        answer += need * cost[cost.length - 1][1];
        return answer;
    }