[백준/Python] 26215 : 눈 치우기

 

쉬워보이지만, 문제 상황에 맞는 적절한 자료구조를 선택하고 주어진 조건을 모두 적절하게 녹여내야 통과할 수 있었던 문제였다. 결론적으론 파이썬의 heapq를 사용해서 음수를 적용한 최대힙으로 구현에 성공하였음

 

 

1. 첫 번째 시도

N = int(input()) # 3
snow = list(map(int, input().split())) # 각 눈 더미의 높이

def cleaning(snow):
    if sum(snow) > 1440:
        print(-1)
        return
    
    snow.sort(reverse=True)
    min = 0 # 치우는 시간
    
    while(len(snow) > 1): # 2개 이상인 경우
        snow[0] -= 1
        snow[1] -= 1
        min += 1
        
        if snow[0] == 0: snow.pop(0)
        if len(snow) > 1 and snow[1] == 0: snow.pop(1)
        snow.sort(reverse=True)
    # 최대 길이 1종류만 남음
    if snow: min += snow[0]
    print(min)

cleaning(snow)

 

처음엔 위와 같이 리스트 슬라이싱으로 작성했는데 시간초과 오류가 발생하였다.

아무래도 우려했던 것처럼 while 루프 안에 매번 snow.sort()로 정렬하는 것이 비효율적이어서 시간 초과 오류가 발생한 것 같았음 (+ 매번 슬라이싱 까지..

따라서 이를 효율적으로 수정하기 위해 우선순위 큐를 사용하여 다음과 같이 구조를 변형해보았다.

 

 

2. 두 번째 시도

import heapq

N = int(input()) # 3
snows = list(map(int, input().split())) # 각 눈 더미의 높이
heap = []
for snow in snows:
    heapq.heappush(heap, -snow)


def cleaning(heap):
    if sum(snows) > 1440:
        print(-1)
        return

    min = 0 # 치우는 시간
    
    while(len(heap) > 1): # 2개 이상인 경우
        first = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        
        first -= 1
        second -= 1
        min += 1
        
        if first > 0:
            heapq.heappush(heap, -first)
        if second > 0:
            heapq.heappush(heap, -second)
    # 눈더미 1종류만 남음
    if heap: min += (-heap[0])
    print(min)

cleaning(heap)

 

이렇게 해서 성공할 줄 알았는데 이 코드도 계속 제출할 때마다 틀렸다고 나왔다.

계속 분석해본 결과 일단 틀렸다고 나온 이유는 다음 두 가지 이유 때문인 것 같았음...

 

1. 눈 치우는 시간의 제한 조건을 잘못 처리

문제에서 눈을 치우는 시간의 제한이 1440분이라고 명시되어 있는데, 현재 코드는 치우는 시간이 1440분을 초과하는 경우에 대해서만 -1 을 출력하도록 작성하였다.

그러나 문제의 요구 사항은 눈을 모두 치우는 데 필요한 시간이 1440분을 초과하면 -1을 출력하라는 것!

즉, 치우는 중간에라도 1440분을 초과하게 되면 즉시 종료하고 -1을 출력해야 한다는 점을 놓쳤던 것 같다.

 

2. 눈 더미를 효과적으로 비교하는 로직에서 부적절한 조건을 넣었음

위 코드는 최대 힙을 사용해서 가장 높은 눈 더미 두 개를 선택해 각각 1씩 줄이고, 반복해서 눈을 치우는 방식으로 구현함

이를 더 간단하게 하면 힙을 사용하지 않고 매번 가장 높은 두 눈 더미를 직접 선택하고 줄이는 방식으로 작성할 수도 있을 것 같았다. 

 

무튼 위 두 사항을 다시 적용해서 최적화해본 결과 다음 정답 코드를 얻을 수 있었다.

 

 

3. 최종 정답 코드 

import heapq

N = int(input())  # 눈 더미의 개수
snows = list(map(int, input().split()))  # 각 눈 더미의 높이

# 눈 높이를 최대 힙으로 변환
heap = []
for snow in snows:
    if snow > 0:
        heapq.heappush(heap, -snow)  # 최대 힙을 위해 음수로 변환

time = 0  # 눈을 치우는 시간

# 눈 치우기 시작
while len(heap) > 1:
    # 가장 큰 눈 더미 두 개를 꺼냄
    first = -heapq.heappop(heap)
    second = -heapq.heappop(heap)

    # 각 눈 더미의 높이를 1씩 줄이고 시간 추가
    first -= 1
    second -= 1
    time += 1

    # 줄어든 눈 더미를 다시 힙에 추가 (높이가 0보다 큰 경우에만)
    if first > 0:
        heapq.heappush(heap, -first)
    if second > 0:
        heapq.heappush(heap, -second)

    # 시간 제한 체크
    if time > 1440:
        print(-1)
        exit()

# 마지막 남은 눈 더미 처리
if heap:
    time += -heap[0]

# 시간 제한 체크
if time > 1440:
    print(-1)
else:
    print(time)

 

일단 함수 구조를 아예 없애버리고 1440분을 초과하는 조건을 while문에 넣음으로써 눈을 치우는 과정에서 time이 1440을 초과하는지 매번 확인하도록 수정했다. 

그리고 남은 눈 더미를 처리한 후에도 시간을 체크하여 1440을 초과할 경우 -1을 출력하도록 수정하였다.