[99클럽 5기 코테 스터디 TIL 18일차] 맥주 축제 (feat. 탐욕법(Greedy))

1) 문제

https://www.acmicpc.net/problem/17503

 

2) 풀이

코드 해석

1. 입력 받기 (BufferedReader 활용)
   • N, M, K 값을 읽고, Beer 객체 배열을 생성하여 K개의 맥주 정보를 저장합니다.
2. 정렬 (도수 레벨 기준 오름차순)
   • Arrays.sort(beers, Comparator.comparingInt(b -> b.alcoholLevel));
   • 도수가 낮은 맥주부터 선택할 수 있도록 정렬합니다.
3. 우선순위 큐 (PriorityQueue) 사용
   • PriorityQueue<Integer> minHeap = new PriorityQueue<>();
   • 최소 힙을 사용하여 현재 선택한 N개 맥주 중 선호도가 가장 낮은 것을 제거합니다.
4. 맥주 선택 및 조건 충족 확인
   • 하나씩 minHeap에 추가하면서 선호도 합을 누적 (sumPreference += beer.preference)
   • N개를 초과하면 poll()을 이용해 가장 작은 값을 제거하여 N개 유지
   • N개를 유지하면서 sumPreference >= M이 되면 현재 도수 레벨을 minAlcoholLevel로 갱신
5. 출력 결과
   • 조건을 만족하는 최소 간 레벨이 minAlcoholLevel에 저장되며, 이를 출력
   • 만족하는 경우가 없다면 -1 출력

시간 복잡도 분석

1. 정렬: O(K log K)
2. 우선순위 큐 삽입/삭제: O(K log N)
3. 총 시간 복잡도: O(K log K + K log N) ≈ O(K log K)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 축제 기간 (N일)
        int M = Integer.parseInt(st.nextToken()); // 필요한 선호도 합
        int K = Integer.parseInt(st.nextToken()); // 맥주 종류 개수

        Beer[] beers = new Beer[K];

        // 맥주 정보 입력받기
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken()); // 선호도
            int c = Integer.parseInt(st.nextToken()); // 도수 레벨
            beers[i] = new Beer(v, c);
        }

        // **도수 레벨 기준 오름차순 정렬**
        Arrays.sort(beers, Comparator.comparingInt(b -> b.alcoholLevel));

        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 선호도 낮은 맥주 제거용
        int sumPreference = 0;
        int minAlcoholLevel = -1;

        // **맥주 탐색 (Greedy 적용)**
        for (Beer beer : beers) {
            minHeap.add(beer.preference);
            sumPreference += beer.preference;

            if (minHeap.size() > N) {
                sumPreference -= minHeap.poll(); // 가장 선호도가 낮은 맥주 제거
            }

            if (minHeap.size() == N && sumPreference >= M) {
                minAlcoholLevel = beer.alcoholLevel;
                break;
            }
        }

        System.out.println(minAlcoholLevel);
    }

    static class Beer {
        int preference;
        int alcoholLevel;

        Beer(int preference, int alcoholLevel) {
            this.preference = preference;
            this.alcoholLevel = alcoholLevel;
        }
    }
}