[백준/ 파이썬] 11509 풍선 맞추기

백준 11509 풍선 맞추기

이 문제를 처음에는 직관적으로 이중 반복문을 통해서 풀면 된다고 생각했습니다.

그러나 시간초과에서 걸렸고 저는 시간복잡도를 개선해야 했습니다.

시간 복잡도를 줄여볼려고 생각은 해봤지만 도저히 떠오르지가 않아서

다른 훌륭한 분들의 코드를 참고했습니다.

제가 이해한 방식으로 다시 아이디어를 풀어보자면.

풍선이 위치한 곳에 화살이 위치해 있는가? 화살이 풍선이 위치한 곳에 있다면

풍선은 터지고 화살의 높이는 1만큼 줄어듭니다.

그리고 화살은 높이가 0이 되지 않는 이상 사라지지 않고 해당 자리에 머물러 있습니다.

그래서 화살이 위치할 수 있는 리스트를 생성한 다음에 0으로 초기화 시켜줍니다.

그리고 풍선의 위치를 인덱스로 하는 화살의 리스트를 방문한 다음

그 위치의 값이 0이라면 화살이 없다는 이야기니까 화살을 추가해주고

해당 위치의 값이 0이 아니라면 화살이 있다는 이야기니까 해당 위치의 화살을 제거해줍니다.

그리고 풍선의 위치에 화살이 있었던 없었던것과는 무관하게 각 반복마다 풍선을 터트리게 되므로 항상 화살의 위치는 -1이 되겠습니다.

n = int(input())

balloon = [int(x) for x in input().split()]
arrow_pos = [0]*(1000000+1)
cnt = 0
for i in range(len(balloon)):
    #해당 위치에 화살이 없을때
    if arrow_pos[balloon[i]] == 0:
        cnt += 1
    #해당 위치에 화살이 있을때
    else:
        arrow_pos[balloon[i]] -= 1
    #해당 위치에 화살이 있으나 없으나 해당위치에서의 화살의 높이는 계속 -1 줄어들것이다.
    arrow_pos[balloon[i] - 1] += 1

print(cnt)