📍 센티와 마법의 뿅망치
💭 센티는 마법 도구들을 지니고 여행을 떠나는 것이 취미인 악당이다.
거인의 나라에 도착한 센티는 자신보다 키가 크거나 같은 거인들이 있다는 사실이 마음에 들지 않았다.
센티가 꺼내 들은 마법 도구는 바로 마법의 뿅망치로, 이 뿅망치에 맞은 사람의 키가 ⌊ 뿅망치에 맞은 사람의 키 / 2 ⌋로 변하는 마법 도구이다. 단, 키가 1인 경우 더 줄어들 수가 없어 뿅망치의 영향을 받지 않는다.
하지만 마법의 뿅망치는 횟수 제한이 있다. 그래서 센티는 마법의 뿅망치를 효율적으로 사용하기 위한 전략을 수립했다. 바로 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다.
과연 센티가 수립한 전략에 맞게 마법의 뿅망치를 이용한다면 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있을까?
입력
첫 번째 줄에는 센티를 제외한 거인의 나라의 인구수 N (1 ≤ N ≤ 105)과 센티의 키를 나타내는 정수 Hcenti (1 ≤ Hcenti ≤ 2 × 109), 마법의 뿅망치의 횟수 제한 T (1 ≤ T ≤ 105)가 빈칸을 사이에 두고 주어진다.
두 번째 줄부터 N개의 줄에 각 거인의 키를 나타내는 정수 H (1 ≤ H ≤ 2 × 109)가 주어진다.
출력
마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수를 출력한다.
마법의 뿅망치를 센티의 전략대로 남은 횟수 전부 이용하고도 거인의 나라에서 센티보다 키가 크거나 같은 거인이 있는 경우, 첫 번째 줄에 NO를 출력하고, 두 번째 줄에 마법의 뿅망치 사용 이후 거인의 나라에서 키가 가장 큰 거인의 키를 출력한다.
풀이
첫 번째 풀이 (힙 X, 시간 초과)
처음에는 최대 힙으로 구현할 생각을 못하고, 문제에서 주어진 그대로 코드를 짰다.
거인들의 키를 내림차순으로 정렬해서 첫 번째 값을 절반으로 나누는 연산을 반복하도록 구현하였다.
# 입력
# 첫 번째 줄 : 인구수 N, 센티의 키 H, 뿅망치 횟수 제한 T
# 다음 N줄 : 각 거인의 키 H
# 출력
# 첫 번째 줄 : 전략 성공 여부(YES/NO)
# 두 번째 줄 : 뿅망치를 최소로 사용한 횟수
N, H, T = map(int, input().split())
# 거인의 키를 저장할 리스트 생성
heights = []
# 입력값을 받음
for _ in range(N):
heights.append(int(input()))
count = 0
# 제일 키가 큰 거인이 센티보다 크고 제한 횟수를 넘지 않은 경우
while max(heights) > H and count <= T:
heights.sort(reverse=True) # 내림차순으로 정렬
largest = heights[0] # 가장 큰 값
# largest 값이 1이면 더 이상 나눌 수 없으므로 종료
if largest == 1:
break
# largest를 2로 나누기
heights[0] = largest // 2
# 시도 횟수 증가
count += 1
# 결과값 출력
if max(heights) < H:
print("YES")
print(count)
else:
print("NO")
print(max(heights))vscode 에서는 정답이 출력되지만 백준에서 시간 초과가 떴다...
멘토님께 질문하니까 sort, max 함수가 시간 복잡도를 증가시켰을 것이라고 하셨다.
파이썬 sort와 max 함수는 반복문과 동일하게 O(n)의 시간 복잡도를 갖는다.
그 이유는 리스트 전체를 탐색하면서 정렬을 구현하고, 최대값을 찾기 때문이다.
그래서 위 코드에서 while문 내에 sort, max를 사용했기 때문에 n 제곱의 시간 복잡도를 가지게 된 것이다.
결국 힙을 쓰도록 유도하는 문제이다.
두 번째 풀이 (힙 O, 틀림)
# 입력
# 첫 번째 줄 : 인구수 N, 센티의 키 H, 뿅망치 횟수 제한 T
# 다음 N줄 : 각 거인의 키 H
# 출력
# 첫 번째 줄 : 전략 성공 여부(YES/NO)
# 두 번째 줄 : 뿅망치를 최소로 사용한 횟수
import heapq
N, H, T = map(int, input().split())
# 거인의 키를 저장할 힙 생성
heights = []
# 입력값을 음수로 변환해서 힙에 추가 (최대힙으로 구현)
for _ in range(N):
heapq.heappush(heights, -int(input()))
# 횟수 초기화
count = 0
# 제일 큰 거인이 센티보다 크고 제한 횟수를 넘지 않은 경우
while heights and (-heights[0] > H) and (count < T):
# 양수로 변환해서 largest에 할당
largest = -heapq.heappop(heights)
# largest를 절반으로 줄이기
new_height = largest // 2
# 음수로 변환해서 힙에 추가
heapq.heappush(heights, -new_height)
# 횟수 증가
count += 1
# largest가 1이면 더 이상 줄일 수 없으므로 종료
if largest == 1:
heapq.heappush(heights, -largest)
break
# 결과값 출력
if -heights[0] < H:
print("YES")
print(count)
else:
print("NO")
print(-heights[0])그래서 힙을 사용한 코드로 수정했는데, 채점하는 데 백만년 걸리더니 마지막에서 틀렸습니다 가 떴다 ㅎㅎ..
계속 들여다봐도 반례를 못 찾겠던 와중..
일단 중간에 largest를 변수에 할당하고 다시 추가하는 구조가 불필요한 것 같아서 좀 더 간단하게 힙 내 요소를 대체할 수 있는 방법이 없을까 검색해 보았다.
그 결과 heapreplace라는 함수가 있다는 것을 알게 됨 !
(결국 틀린 이유는 못 찾았다. 나중에 다시 멘토님께 질문 예정)
세 번째 풀이 (힙 O, 정답)
# 입력
# 첫 번째 줄 : 인구수 N, 센티의 키 H, 뿅망치 횟수 제한 T
# 다음 N줄 : 각 거인의 키 H
# 출력
# 첫 번째 줄 : 전략 성공 여부(YES/NO)
# 두 번째 줄 : 뿅망치를 최소로 사용한 횟수
import heapq
N, H, T = map(int, input().split())
# 거인의 키를 저장할 힙 생성
heights = []
# 입력값을 음수로 변환해서 힙에 추가 (최대힙으로 구현)
for _ in range(N):
heapq.heappush(heights, -int(input()))
# 횟수 초기화
count = 0
# 뿅망치 제한 횟수만큼 반복
for _ in range(T):
# 제일 큰 거인의 키가 1이 아니고 센티의 키보다 같거나 큰 경우
if -heights[0] != 1 and -heights[0] >= H:
# heights에서 최소값을 제거하고 2로 줄인 값으로 다시 넣어주기
heapq.heapreplace(heights, -(-heights[0] // 2))
# 횟수 증가
count += 1
# 결과값 출력
if -heights[0] < H:
print("YES")
print(count)
else:
print("NO")
print(-heights[0])heapreplace 함수를 사용해서 코드를 줄이고, while문 부분도 조건처럼 사용하는 대신 뿅망치 횟수 제한만큼 for문을 반복하도록 수정해주었다.
그랬더니 정답 성공 !
새롭게 알게 된 것
1. 시간 복잡도를 줄이는 방법
- 파이썬 sort 함수는 배열 내 모든 원소를 탐색하여 정렬한다.
- 이는 반복문과 동일하게 O(n)의 시간 복잡도를 가지므로, 힙 자료구조에 비해 훨씬 큰 시간 복잡도가 소요된다.
- max / min 역시 배열 내 모든 원소를 탐색해서 최소 / 최대값을 찾는다.
- 따라서 시간 복잡도를 줄이기 위해서는 sort, max, min 함수는 지양하는 것이 좋다.
2. heapq 주요 메서드
- heapify(lst) : 리스트를 힙으로 변환
import heapq
heapq.heapify(lst)- heappush(heap, item) : heap 에 item 추가
import heapq
heapq.heappush(heap, item)- heappop(heap) : heap 에서 최소값을 제거하고 반환
import heapq
heapq.heappop()- heapreplace(heap, item) : heap 에서 최소값을 제거하고 item을 추가
import heapq
heapq.heapreplace(heap, item)