99클럽 코테 스터디 25일차 TIL + 우선순위 큐, 최대 힙

임정민·2025년 2월 24일

[99클럽5기] - 1일 1코테

목록 보기

25/26

1. 문제

[문제 설명]

송이는 이번 학기에 할 일이 매우 많다. $N$ 개의 일 중 어떤 일부터 해야 할지 고민하던 중 송이에게 좋은 아이디어가 떠올랐다! 바로 해야 할 일 각각의 중요도를 산정하고, 중요도가 높은 일부터 하는 것이다. 송이는 하루에 하나의 일만 처리할 수 있으며, 일을 처리한 후 그 일의 중요도는 $M$ 만큼 감소한다. 일의 중요도가 $K$ 이하가 되면 그 일은 완료한 것으로 간주한다. 중요도를 일별로 산정하던 중 송이는 문득 일하면서 본인이 매일 느낄 만족감이 궁금해졌다. 오늘의 만족감은 전날의 만족감을 $Y$ , 오늘 할 일의 중요도를 $P$ 라 할 때 $\lfloor Y/2 \rfloor+P$ 와 같다.

예를 들면 다음과 같다. 전날 송이의 만족도가 $21$ 이고, 송이가 오늘 할 일의 중요도가 $10$ , $M$ 의 값이 $4$ 라고 가정했을 때 송이가 오늘 느낄 만족감은 $\lfloor \frac{21}{2} \rfloor+10$ = $20$ 이 된다. 이후 송이가 오늘 한 일의 중요도는 $4$ 만큼 감소해서 $6$ 이 된다.

송이가 해야 할 일의 개수 $N$ , 일을 처리했을 때 감소하는 중요도 $M$ , 완료한 것으로 간주하는 중요도의 최댓값 $K$ 가 주어진 후, $i$ 번 일이 가지는 중요도 $D_i$ 가 입력으로 $N$ 개 주어진다. 송이가 모든 일을 끝낼 때까지 며칠이 걸리는지, 그리고 모든 일을 끝낼 때까지 송이가 일별로 느낀 만족감을 한 줄마다 출력하자. 단, 첫날의 경우 전날의 만족감을 $0$ 으로 간주한다.

[입력]

첫째 줄에 정수 $N$ , $M$ , $K$ 가 공백으로 구분되어 주어진다. $(2 \leq N \leq 2 \, 000; 1\leq M \leq 5; 1 \leq K \leq 3)$

둘째 줄부터 $N$ 개의 줄에 걸쳐 해야 하는 일의 중요도 정수 $D_i$ 가 주어진다. $(M< D_i, K < D_i, D_i \leq 1 \, 000)$

[출력]

첫째 줄에 송이가 일을 다 하기 위해 걸리는 날의 수를 출력한다.

둘째 줄부터 일을 끝내는 날까지 일별로 느낀 만족감을 한 줄씩 구분해 출력한다.

[입출력 예]

2. 풀이

import sys
import heapq

N, M, K = map(int, sys.stdin.readline().split())
task = []

# 최대 힙을 만들기 위해 음수로 변환하여 저장
for _ in range(N):
    D = int(sys.stdin.readline().strip())
    heapq.heappush(tasks, -D)  # 최대 힙처럼 사용하기 위해 음수로 삽입

days = 0  # 일을 끝내는 데 걸리는 총 일수
satisfaction = 0  # 전날 만족도
satisfaction_list = []  # 각 날의 만족도를 저장할 리스트

# 모든 일이 끝날 때까지 반복
while tasks:
    days += 1
    P = -heapq.heappop(tasks)  # 가장 중요한 일 선택 (음수 → 양수 변환)
    satisfaction = (satisfaction // 2) + P  # 오늘의 만족감 계산
    satisfaction_list.append(satisfaction)  # 만족감을 리스트에 추가

    P -= M  # 중요도 감소
    if P > K:
        heapq.heappush(tasks, -P)  # 다시 힙에 추가 (음수 변환)

# 결과 출력
print(days)
print("\n".join(map(str, satisfaction_list)))

3. 회고

3-1. 문제 해결 과정

기본적으로 최소 힙이 적용되기 때문에 가장 중요도가 높은 일부터 처리하기 위해 음수로 삽입하여 최대 힙처럼 사용했다.

import sys
import heapq  # 우선순위 큐 사용

N, M, K = map(int, sys.stdin.readline().split())  # N = 해야 할 일 개수, M = 중요도 감소량, K = 완료 기준
tasks = []

for _ in range(N):
    D = int(sys.stdin.readline().strip())  # 해야 할 일의 중요도 입력
    heapq.heappush(tasks, -D)  # 최대 힙을 만들기 위해 중요도를 음수(-)로 저장

그 다음에는 가장 높은 중요도를 가진 일을 음수 부호를 붙여 불러온 다음(원상 복구), 오늘의 만족감을 계산하고 이를 리스트에 추가해서 만족도를 기록했다. 일을 하게 되면 중요도가 감소한다 했으니 역시 중요도도 같이 줄였다. 이를 while 문에서 반복하면서 일을 해낼 수 있도록 했다.

while tasks:  # 모든 일이 끝날 때까지 반복
    days += 1
    P = -heapq.heappop(tasks)  # 가장 높은 중요도의 일을 선택 (음수 → 양수 변환)

    # 오늘 만족도 계산
    satisfaction = (satisfaction // 2) + P
    satisfaction_list.append(satisfaction)  # 만족도를 리스트에 저장

    P -= M  # 중요도 감소
    if P > K:  # 중요도가 K보다 크면 다시 해야 하는 일
        heapq.heappush(tasks, -P)  # 다시 힙에 추가 (음수 변환)

마지막으로 중요도가 K 이하가 될 때까지 일을 해야 한다고 했으니 앞에서 heapppop(tasks) 했던 부분을 다시 복구할 필요가 있다. 이는 heappush(tasks, -P)를 통해 적용했다. 코드가 실행되는 과정은 아래의 사진을 참고하면 쉽게 이해할 수 있을 것이다.

3-2. 스터디 완주 후기

처음에는 5일 연속 출석도 하고 정말 꼼꼼히 공부했었는데 3 ~ 5주차가 되니 대회에 자격증 시험까지 같이 병행하기 쉽지 않았다. 결국 문제 풀이와 TIL도 이제서야 작성하게 되는 불상사가 발생했다. 그래도 문제도 다 풀어보고 풀이 회고도 했으니 다행이다.

서비스 개발은 많이 해봤어도 알고리즘은 언제나 어렵게 느껴졌기 때문에 올해는 그런 한계들을 넘어보고 싶어서 스터디에 참여하게 되었다. 5주 동안 정말 많은 것을 배웠고 이제 알고리즘 문제도 더 이상 무섭지 않아졌기 때문에 얻어가는 것이 많은 스터디였다는 생각이 들었다.

멘토링 수업으로 인해 매주 월요일에 진행했던 라이브 클래스는 실시간으로 참여하지는 못했지만 이후 영상을 다시 보면서 문제도 풀어보니 실력이 늘 수 있었던 것 같다. 앞으로는 자료구조에 대해 공부하면서 알고리즘 문제를 더 풀어볼 계획이다. 코드 작성에는 문제가 없지만 항상 자료구조 기초 지식이 부족했던 것이 큰 어려움이었기 때문이다.