99클럽 코테 스터디_4기 21일차 TIL

TODAY TIL

안녕하세요! 오늘은 선물 더미에서 가장 많은 선물을 가져가고 남은 선물을 계산하는 문제를 풀어보겠습니다. 이 문제는 선물 더미 중 가장 큰 값을 선택하고, 해당 더미에서 ⌊제곱근⌋만 남기고 나머지를 가져가는 과정을 k초 동안 반복한 후 남은 선물의 총합을 구하는 문제입니다.

문제 설명

문제

주어진 정수 배열 gifts는 다양한 더미에 있는 선물의 개수를 나타냅니다. 매초마다 가장 많은 선물이 있는 더미를 선택하여 ⌊제곱근⌋만 남겨두고 나머지를 가져갑니다. k초 동안 이 작업을 반복하고 최종적으로 남은 모든 선물의 총합을 반환합니다.

 

예시

입력

gifts = [25, 64, 9, 4, 100]
k = 4

 

출력

29

 

설명

• 첫 번째 초: 100을 선택하여 ⌊√100⌋ = 10을 남김 → [25, 64, 9, 4, 10]
• 두 번째 초: 64를 선택하여 ⌊√64⌋ = 8을 남김 → [25, 8, 9, 4, 10]
• 세 번째 초: 25를 선택하여 ⌊√25⌋ = 5를 남김 → [5, 8, 9, 4, 10]
• 네 번째 초: 10을 선택하여 ⌊√10⌋ = 3을 남김 → [5, 8, 9, 4, 3]
• 최종 남은 선물의 총합: 29

문제 풀이

접근 방법

• gifts 배열을 최대 힙(max heap)으로 변환하여 가장 큰 값을 효율적으로 가져옵니다.
• k번 동안 가장 큰 값의 선물을 가져가고 남은 ⌊제곱근⌋ 값을 다시 힙에 넣습니다.
• heapq 모듈을 활용해 효율적으로 최대값을 찾고, ⌊제곱근⌋을 계산하여 힙을 업데이트합니다.

코드 구현

다음은 문제를 해결하기 위한 Python 코드입니다.

import heapq
import math

def remaining_gifts(gifts, k):
    # 최대 힙으로 변환하기 위해 음수로 저장
    max_heap = [-gift for gift in gifts]
    heapq.heapify(max_heap)
    
    for _ in range(k):
        # 가장 큰 값 꺼내기
        max_gift = -heapq.heappop(max_heap)
        # 제곱근을 구해 남은 선물 수 계산
        remaining_gift = math.floor(math.sqrt(max_gift))
        # 남은 선물 다시 힙에 삽입
        heapq.heappush(max_heap, -remaining_gift)
    
    # 남은 선물의 총합 구하기
    return -sum(max_heap)

# 예시 실행
print(remaining_gifts([25, 64, 9, 4, 100], 4))  # 출력: 29
print(remaining_gifts([1, 1, 1, 1], 4))  # 출력: 4

 

코드 설명

1. gifts 배열을 최대 힙으로 변환합니다. Python의 heapq는 최소 힙만 지원하므로 음수로 값을 넣어 최대 힙처럼 사용합니다.
2. k번 반복하며, 가장 큰 값을 꺼내 ⌊제곱근⌋을 계산한 후 다시 힙에 넣습니다.
3. 모든 작업이 끝난 후 힙에 남은 값들을 합산하여 반환합니다.

시간 복잡도

• 힙을 사용하는 삽입 및 삭제의 시간 복잡도는 O(log n)이며, 이를 k번 반복하므로 전체 시간 복잡도는 O(k log n)입니다.

결론

이 코드는 주어진 문제 조건을 충족하면서 효율적으로 풀 수 있는 방법을 제시합니다. heapq와 math 모듈을 적절히 사용하여 최대값을 찾고 갱신하는 과정을 손쉽게 구현할 수 있습니다.

---

이 글이 여러분의 문제 해결에 도움이 되었기를 바랍니다. 질문이나 추가적인 설명이 필요하면 댓글로 남겨주세요!