[백준] 11509번 풍선 맞추기

💡문제접근1

• 필요한 화살의 최소 개수를 구하는 문제다. 일단 가장 높은 지점에 있는 풍선부터 하나씩 쏴서 1씩 감소하는 지점이 가장 높은 지점 이후에 존재하면 화살로 풍선을 맞추는 것을 한 회씩 돌리고 결국 모든 풍선이 터지는 시점까지 반복문을 돌려 필요한 화살의 개수를 출력하면 된다고 생각하여 그대로 접근했다. 근데 시간초과가 발생하여 대체 어떤 접근 방법으로 접근을 해야할지 많이 힘들었다.

💡코드1(시간초과)

import sys
input = sys.stdin.readline

N = int(input())
Ballon = list(map(int, input().strip().split()))
arrow = 0

while True:
	# 풍선이 위치한 가장 높은 지점
    Max_idx = Ballon.index(max(Ballon))
    Max_ballon = max(Ballon)
	
    # 만약 풍선이 다 터졌다면?
    if sum(Ballon) == 0:
        break

    for i in range(Max_idx, len(Ballon)):
        if Max_ballon == Ballon[i]:
            Max_ballon -= 1
            Ballon[i] = 0
    # 필요한 화살의 개수를 출력
    arrow += 1
print(arrow)

• 배열 Ballon에는 최대 1,000,000까지의 입력 개수가 들어올 수 있는데 이 때, index를 사용하여 시간초과가 발생하는 것 같다.

💡소요시간 : 38m

💡문제접근2

• 화살이 날아가는 높이를 계속해서 기록하는 방법이다.
• 테스트케이스를 기준으로 설명하면 다음과 같다.

💡코드2(메모리 : 130636KB, 시간 : 480ms)

import sys
input = sys.stdin.readline

N = int(input())
ballon = list(map(int, input().strip().split()))
arrow = [0] * 1000001

result = 0
for i in range(N):
    if arrow[ballon[i]] == 0:
        result += 1
    else:
        arrow[ballon[i]] -= 1
    arrow[ballon[i]-1] += 1
print(result)

# 1차원 배열을 이용한 관리
# 2 1 5 4 3
# 2 : 화살 한 개 필요
# 1 : 높이가 2이면 높이가 1인 지점의 풍선도 제거 가능

# 5 : 화살 한 개 필요
# 4 : 높이가 5면 높이가 4인 지점의 풍선도 제거 가능
# 3 : 높이가 4면 높이가 3인 지점의 풍선도 제거 가능

💡소요시간 : 28m