처음에 이 문제에 접근할때에는 풍선이 없어질 때까지 반복하는 while문 안에서 풍선을 뒤에서부터 확인하며 자신의 앞의 풍선이 더 클 경우에는 계속해서 풍선을 지우고 더 작다면 cnt변수를 증가시켜 cnt변수를 출력하는 방식으로 작성하였다. 그러나 시간 복잡도가 O(n^2)가 되었고 화살이 다음 풍선을 못터트려도 안없어지고 계속 날아가는 것을 인지하지 못해 오답 처리 되었다.

O(n)에 해결할 수 있는 방법이 뭐가 있을지 생각하다가 화살이 존재하는 높이를 표시하는 배열을 만들어 화살의 개수를 관리하기로 하였다. 풍선의 높이에 화살이 있을 경우에는 화살을 풍선의 높이-1로 이동시키고 풍선의 높이에 화살이 없을 경우에는 화살을 생성하는 방식이다. 이렇게 화살을 모두 이동/생성한 뒤에 화살이 존재하는 높이를 표시하는 배열의 총 합을 구하면 화살의 갯수를 구할 수 있다.

• n을 입력받는다.
• 풍선의 높이 h 배열을 입력받는다.
• 화살이 존재하는 높이를 표시할 배열 arrow를 0 n+1개로 구성한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> 만약 arrow[h[i]]가 존재할 경우,
  --> arrow[h[i]]를 1 빼준다. (화살의 이동)
  --> arrow[h[i]-1]을 1 더해준다. (화살의 이동)
  -> 존재하지 않을 경우 arrow[h[i]-1]을 1 더해준다. 이는 화살이 h[i] 풍선을 터트리고 다음 높이로 이동한 것을 나타낸다.
• arrow의 총합을 출력한다.

Code

n=int(input())
h=list(map(int, input().split()))
arrow=[0]*(n+1)
for i in range(n):
    if arrow[h[i]]:
        arrow[h[i]]-=1
        arrow[h[i]-1]+=1
    else:
        arrow[h[i]-1]+=1
print(sum(arrow))

테스트 케이스는 모두 제대로 출력하지만 오답처리가 계속 되어서 틀린 부분을 찾기 위해 제출을 여러번 했다... 다음에는 조금 더 신중하게 확인하고 제출하기..!!