백준_11509_풍선 맞추기(python)

※ 접근

 풍선의 갯수가 최대 백 만개였고 데이터를 정렬시킬 수도 없었기 때문에 그리디 알고리즘으로 풀어야겠다고 생각했다.

 

※ 풀이

1. defaultdict를 이용해서 해당 바늘이 key에 존재하지 않거나 value가 0이라면 결과값을 + 1을 해주고 해당 바늘 -1한 값을 key로 만들어줬다.

2. 해당 바늘이 있었다면 value -1을 해주고 해당 바늘 높이 -1한 값을 key로 만들어줬다.

 

from collections import defaultdict
import sys
input = sys.stdin.readline

n = int(input())

data = list(map(int,input().split()))

s = defaultdict(int)

count = 0

for i in data:
    if i not in s or s[i] == 0:
        s[i-1] += 1
        count += 1
    else:
        s[i] -= 1
        s[i-1] += 1
    
print(count)

※ 회고

 처음에 사전형이 아닌 set()을 이용해서 풀었다. set을 이용할 시 중복된 높이에 대해서는 처리를 하지 못하기 때문에 결과값이 기댓값보다 증가됐다. set을 사용할 때는 중복값에 대해 주의하자!!!