99클럽 코테 스터디 21일차 TIL + 오늘의 학습 키워드 : 힙

항해99_ 21일차 문제
백준 19638번_센티와 마법의 뽕망치

관련 키워드 : 힙
어떤 자료구조로 접근했는지? : 최대 힙

 

문제

정답코드
: 파이썬에서는 기본적으로 최소힙 기준으로 메서드를 제공한다.
그렇기에 최대힙 구현을 위해서는 '음수'를 적용해서 사용해줘야한다 
이것은 TIP 나도 몰랐던 것.

import sys
import heapq

def main():
    input = sys.stdin.readline  # 빠른 입력을 위해 사용
    line = input().split()
    N = int(line[0])
    H = int(line[1])
    T = int(line[2])
    
    pq = []  # 최대 힙을 위한 리스트

    for _ in range(N):
        height = int(input().strip())
        heapq.heappush(pq, -height)  # 최대 힙을 위해 음수로 저장

    time = 0
    while time < T:
        if not pq:  # 힙이 비어 있는지 확인
            break
        
        height = -pq[0]  # 가장 큰 거인의 키 가져오기 (음수로 저장했으므로 다시 음수로 변환)
        
        if height < H or height == 1:
            break
        
        # 뿅망치로 맞은 후 키 삽입
        heapq.heappop(pq)  # 가장 큰 거인 제거
        heapq.heappush(pq, -(height // 2))  # 키를 반으로 줄여서 다시 추가
        time += 1

    if pq and -pq[0] < H:  # 힙이 비어 있지 않고 가장 큰 거인의 키가 H보다 작으면
        print("YES")
        print(time)
    else:
        print("NO")
        print(-pq[0] if pq else 0)  # 힙이 비어 있지 않으면 가장 큰 거인의 키 출력, 비어 있으면 0 출력

if __name__ == "__main__":
    main()

코드 설명
1.입력 처리: sys.stdin.readline을 사용하여 입력을 빠르게 처리합니다.
2.최대 힙 구현: heapq를 사용하여 최대 힙을 구현하기 위해 모든 높이를 음수로 저장합니다.
3.주요 로직: 주어진 시간 T 동안 반복하며, 가장 큰 거인의 키를 확인하고, 조건에 따라 키를 반으로 줄입니다.
4.결과 출력: 센티의 키가 가장 큰 거인보다 크면 "YES"와 시간을 출력하고, 그렇지 않으면 "NO"와 가장 큰 거인의 키를 출력합니다.

 

Python 코드에서 사용된 메서드와 로직에 대해 자세히 설명해드리겠습니다.

<사용된 메서드 및 설명>
sys.stdin.readline:

이 메서드는 표준 입력으로부터 한 줄을 읽어오는 함수입니다. 
input()보다 빠른 입력을 제공하여 대량의 데이터를 처리할 때 유용합니다.

사용 예: line = input().split()은 입력된 한 줄을 공백으로 나누어 리스트로 반환합니다.

heapq 모듈:

Python의 heapq 모듈은 최소 힙(min-heap) 자료구조를 제공합니다. 

최대 힙(max-heap)을 구현하기 위해 음수 값을 사용합니다.

---

<주요 메서드>
heapq.heappush(heap, item): 힙에 새로운 항목을 추가합니다.
heapq.heappop(heap): 힙에서 가장 작은 항목을 제거하고 반환합니다. 최대 힙을 구현하기 위해 음수로 저장된 값을 사용하여 가장 큰 값을 얻습니다.
heapq.heapify(x): 리스트 x를 힙으로 변환합니다.

리스트와 음수 사용:

최대 힙을 구현하기 위해 모든 높이를 음수로 변환하여 저장합니다. 

예를 들어, 높이가 10인 거인을 추가할 때 -10을 저장합니다. 

이렇게 하면 heapq의 기본 동작(최소 힙)을 이용하여 최대 힙처럼 동작하게 됩니다.

로직 설명
1. 입력 처리:
첫 번째 줄에서 N, H, T를 읽어옵니다. N은 거인의 수, H는 센티의 키, T는 주어진 시간입니다.
다음 N줄에서 각 거인의 키를 읽어와 최대 힙에 추가합니다.

2. 시간 루프:
time 변수를 0으로 초기화하고, 주어진 시간 T 동안 반복합니다.
매 반복마다 현재 최대 힙의 가장 큰 값(가장 높은 거인의 키)을 확인합니다.
만약 이 값이 H보다 작거나 1이라면 루프를 종료합니다. 이는 센티가 이길 수 있는 조건입니다.

3. 거인의 키 감소:
가장 큰 거인의 키를 반으로 줄입니다. 이를 위해 heapq.heappop(pq)로 가장 큰 값을 제거하고, 그 값을 반으로 나눈 후 다시 음수로 변환하여 힙에 추가합니다.
time을 1 증가시킵니다.

4. 결과 출력:
루프가 종료된 후, 힙의 가장 큰 값이 H보다 작으면 "YES"와 시간을 출력합니다.
그렇지 않으면 "NO"와 현재 가장 큰 거인의 키를 출력합니다. 힙이 비어 있을 경우 0을 출력합니다.

예시
예를 들어, 입력이 다음과 같다고 가정해 보겠습니다:


3 5 10
10
8
6
N = 3, H = 5, T = 10입니다.

거인의 키는 10, 8, 6입니다.
첫 번째 반복에서 가장 큰 키는 10입니다. 10을 반으로 줄여 5로 만들고, time을 1 증가시킵니다.
두 번째 반복에서 가장 큰 키는 8입니다. 8을 반으로 줄여 4로 만들고, time을 2 증가시킵니다.
세 번째 반복에서 가장 큰 키는 6입니다. 6을 반으로 줄여 3으로 만들고, time을 3 증가시킵니다.
이후 반복에서 가장 큰 키는 5입니다. 5는 센티의 키와 같으므로 루프가 종료됩니다.
최종적으로 가장 큰 키는 5로, "YES"와 함께 time인 3이 출력됩니다.
이와 같은 방식으로 코드는 주어진 조건을 만족하는지 확인하고 결과를 출력합니다.