[IT/코딩테스트] 99클럽 코테 스터디18일차 TIL + BOJ17503

 

오늘의 문제

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

 

 

오늘도 문제를 오랜 시간 고민하기 보다는 다른 분들의 풀이를 분석하면서 공부했다. 🥹

내일 중요한 일정이 있어서 그걸 준비하느라 오늘 최대한 시간을 아껴야한다...

 

근데 또 내일 ~ 20 까지는 해커톤 .... 🔥🔥🔥 몰라~ 다 끝나고 코테 공부 열심히 하자~~~~

 

위의 문제에 대해서 서칭을 하던 중, 여러 풀이 방법을 보게 되었다.

거의 대부분이 우선순위큐 방식의 풀이였고, 중간중간 이분탐색 방법이 보였다. 이분탐색은 시간 초과되는 경우가 많아서 많이 없는 것으로 파악. (이분탐색이 시간초과가 나서 우선순위큐로 해결했다는 글들을 보았다😸)

 

참고한 글들은 아래와같다.

---

 

** 자료구조, 우선순위큐 **

 

https://bluehyena.tistory.com/entry/%EB%B0%B1%EC%A4%80-17503%EB%B2%88-%EB%A7%A5%EC%A3%BC-%EC%B6%95%EC%A0%9C-Python

[백준 17503번] - 맥주 축제 / Python

 

 

** 이분탐색 **

 

https://bluehyena.tistory.com/entry/%EB%B0%B1%EC%A4%80-17503%EB%B2%88-%EB%A7%A5%EC%A3%BC-%EC%B6%95%EC%A0%9C-Python

[백준 17503번] - 맥주 축제 / Python

 

---

오늘 공부한 내용 : 코드 분석

**우선순위 큐(최소 힙) 와 정렬 기법**을 사용하여

"최소한의 간 레벨로 N일 동안 선호도 M 이상을 만족하는 맥주를 선택하는 방법"을 구하는 알고리즘

 

1. 입력 처리 및 정렬

import sys
import heapq

n, m, k = map(int, sys.stdin.readline().split())

# 선호도 순서로 정렬하여 입력
beers = [list(map(int, input().split())) for _ in range(k)]
beers = sorted(beers, key=lambda x: (x[1], x[0]))

• n: 축제 기간 (마셔야 할 맥주의 수)
• m: 요구되는 선호도의 합
• k: 제공되는 맥주의 종류
• beers: 각 맥주의 (선호도, 도수 레벨) 정보를 담은 리스트
• 정렬 기준: (도수 레벨, 선호도) 순으로 오름차순 정렬
  • 같은 도수 레벨일 경우 선호도가 낮은 순으로 정렬
  • 이렇게 정렬하는 이유는 "낮은 도수부터 마시면서 조건을 만족하는 최솟값을 찾기 위해서"

 

2. 맥주 선택 및 우선순위 큐 활용

preference = 0
pq = []

# 낮은 도수부터 먹어보면서 N을 만족하는지 확인
# 만족하지 않으면 -1 출력하고 종료
for i in beers:
    preference += i[0]
    heapq.heappush(pq, i[0])

    if len(pq) == n:
        if preference >= m:
            answer = i[1]
            break
        else:
            preference -= heapq.heappop(pq)
else:
    print(-1)
    exit()

print(answer)

 

📌 핵심 로직 분석

1. 현재 선택한 맥주의 선호도 총합 preference 유지
   • preference += i[0]: 현재 선택한 맥주의 선호도를 더함
   • heapq.heappush(pq, i[0]): 우선순위 큐(최소 힙)에 현재 맥주의 선호도를 추가
2. N개를 다 선택한 경우 체크
   • if len(pq) == n:
     • 현재 선택한 맥주가 정확히 N개가 되었다면,
     • preference >= m인지 확인해 조건을 만족하는지 판단
     • 만족한다면, 현재 맥주의 도수 i[1]를 answer에 저장하고 종료
3. 조건을 만족하지 않으면 가장 선호도가 낮은 맥주를 제거
   • preference -= heapq.heappop(pq):
     • 현재 선택한 맥주의 개수가 N개를 넘어가면,
     • 최소 힙에서 가장 선호도가 낮은 맥주를 제거
     • 즉, N개를 유지하면서 최적의 조합을 찾는 과정
4. 모든 맥주를 탐색했음에도 조건을 만족하는 조합이 없다면 -1 출력
   • else문 내부에서 print(-1) 후 exit()로 종료
5. 조건을 만족하면 answer 출력
   • print(answer)

---

🔍 알고리즘 핵심 아이디어

1. 맥주를 도수 기준 오름차순 정렬
   • "최솟값을 찾아야 하기 때문에" 낮은 도수부터 탐색
2. 우선순위 큐(최소 힙)를 활용한 맥주 선호도 관리
   • 우선순위 큐는 항상 현재 선택한 맥주 중 가장 선호도가 낮은 맥주를 유지
   • N개를 유지하면서 최적의 조합을 찾아 나감
3. N개를 만족할 때마다 선호도 총합이 M 이상인지 확인
   • 만족하면 현재 맥주의 도수 레벨을 저장
   • 만족하지 않으면 가장 낮은 선호도의 맥주를 버리고 다음 맥주를 탐색

---

📈 시간 복잡도 분석

1. 맥주 정렬: O(K log K)
2. 맥주 탐색: O(K log N)
   • 매 반복마다 최소 힙 연산(삽입, 삭제)이 일어나므로 O(log N)
3. 전체 복잡도:
   • O(K log K + K log N)
   • 대략적으로 O(K log K)에 가깝다
   • K는 최대 200,000이므로 O(K log K)는 충분히 처리 가능

---

✅ 정리

• 도수 레벨이 낮은 맥주부터 마시면서 조건을 만족하는 최솟값을 찾는다.
• 우선순위 큐(최소 힙)를 사용해 N개를 유지하면서 최적의 맥주 조합을 유지한다.
• 시간 복잡도는 O(K log K), 충분히 효율적이다.
• 정렬 후 탐색하며 선호도가 낮은 맥주를 제거하면서 조건을 만족하는 조합을 만든다.

---

해결 코드

import sys
import heapq

input = sys.stdin.readline

n,m,k = map(int,input().split())

beers = [list(map(int, input().split())) for _ in range(k)]
beers = sorted(beers, key=lambda x: (x[1],x[0]))

preference = 0
pq = []

for i in beers:
    preference += i[0]
    heapq.heappush(pq, i[0])

    if len(pq) == n:
        if preference >= m:
            answer = i[1]
            break
        else:
            preference -= heapq.heappop(pq)
else:
    print(-1)
    exit()

print(answer)

 

 

나중에 우선순위큐 도 제대로 공부하자.

얼마전에 '탭고리즘' 이라고, 항해99에서 알려준 플러그인이 있는데, 거기서 알려준 문제에서  우선순위큐 가 사용되었었다.

다시 보니 반갑구만 🤭🍀

 

어라라...