[백준] 11509 - 풍선 맞추기 (Python)

https://www.acmicpc.net/problem/11509

1) 아이디어

• 주어진 풍선을 재배치할 수는 없기 때문에, 이미 쏘아진 화살들로 남은 풍선을 처리할 수 없으면 무조건 새 화살을 쏘아야 한다.
• 현재 날고 있는 화살의 현재 높이들을 관리하기보다는 현재 높이의 화살이 몇 개 있는지로 접근하는 것이 간편하고 빠르다.

2) 풀이

*성능 기준 상위권 풀이는 아니다.

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
arrow = {}
ans = 0
for h in map(int, input().split()):
    if arrow.get(h, 0):
        arrow[h] -= 1
    else:
        ans += 1
    arrow[h-1] = arrow.get(h-1, 0) + 1

print(ans)

arrow라는 이름으로 딕셔너리를 선언해 높이별 화살의 상태를 관리하고, 풍선의 높이 h에 대한 화살의 존재유무에 따라 카운팅을 변경한다. 화살의 총 개수는 ans 변수로 관리한다.

2-1. h 높이인 화살이 있을 때 ( if절 )

dict.get(x, y) 메소드는 딕셔너리에 키 x가 있는 경우에는 해당 값을 반환하고, 없는 경우에는 default value y를 반환한다. 따라서 arrow[h]가 0이 아닌 경우(=화살이 존재하는 경우) 해당 값을 감산한다.

2-2. h 높이인 화살이 없을 때 ( else절 )

새로운 화살을 쏘고 ans 를 증가시킨다.

화살를 새로 쏘았는지 여부를 떠나 현재 높이의 풍선을 터뜨렸기 때문에 화살의 높이는 h-1이 된다. 따라서 다음 문장을 통해 arrow[h-1]을 증가시킨다.

arrow[h-1] = arrow.get(h-1, 0) + 1

arrow.get(h-1, 0)을 호출해 대입하는 이유는, arrow[h-1]의 값이 없는 경우 키 에러가 발생하기 때문이다.

참고 - defaultdict를 사용한 풀이

위 코드를 dict.get() 대신 defaultdict로 작성한 풀이이다.

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

n = int(input())
arrow = defaultdict(int)
ans = 0
for h in map(int, input().split()):
    if arrow[h]:
        arrow[h] -= 1
    else:
        ans += 1
    arrow[h-1] += 1

print(ans)

두 코드의 채점 결과를 비교하면 dict.get()을 사용한 코드가 미세하게 성능이 더 좋다.

방식	메모리	시간
dict.get() 사용	86320 KB	508 ms
defaultdict 사용	87332 KB	520 ms

defaultdict 인스턴스 선언시에는 기본 팩토리 메소드를 생성하는데, 조회하는 데이터의 성격에 따라 여기서 오버헤드로 작용할 수 있다.

일반 딕셔너리에서 dict.get()을 사용해 없는 키를 조회하는 경우에는 y를 반환하고 딕셔너리의 아이템이 변경되지 않지만, defaultdict에서 없는 키가 조회되는 경우에는 해당 키가 새로 추가되기 때문이다.

일반 딕셔너리 dict_a와 defaultdict로 선언한 dict_b의 동작을 비교해보자.

>>> dict_a = {'A':1, 'B':2, 'C':3}

#dict_a에서 키 'D'를 조회한 후 해당 값이 없으면 0 반환
>>> dict_a.get('D', 0)
0

>>> dict_a
{'A': 1, 'B': 2, 'C': 3}

다음은 defaultdict 객체 dict_b이다.

>>> from collections import defaultdict

# 선언 생략
>>> dict_b
defaultdict(<class 'int'>, {'A': 1, 'B': 2, 'C': 3})

>>> dict_b['D']
0

>>> dict_b
defaultdict(<class 'int'>, {'A': 1, 'B': 2, 'C': 3, 'D': 0})

비교

자료들을 찾아보니 defaultdict의 이점은 높은 가독성과 간결성에 있고, 이를 위해 약간의 성능 저하를 감수하는 것이 주류 의견인 듯 하다. 물론 작업과 자료의 특성에 따라 성능은 달라질 수 있다.

참고 : OrderedDict vs defaultdict vs dict
*python3.6부터는 기본 딕셔너리가 collections.OrderedDict와 동일하게 동작한다.

defaultdict 사용은 매우 편리하고 다양하게 활용할 수 있지만, (코딩테스트 채점 결과 등에서는) 사용하지 않은 경우에 비해 메모리 사용량이 높거나 시간이 더 걸릴 때가 많았다.

위의 동작 비교를 바탕으로, 다음과 같은 상황에서는 defaultdict의 오버헤드가 좀 더 클 수 있다.

• 키의 존재 여부에 따라 값 조작 빈도가 달라지거나, 실제로는 다른 키의 값을 조작하는 경우

  • defaultdict에서 존재하지 않는 키를 조회하는 경우 조회와 동시에 아이템을 생성하기 때문에 조작 또는 사용하지 않을 값에 대한 키를 조회했을 경우 불필요한 메모리를 차지하게 된다.
  • 키 a를 조회하고 존재 여부에 따라 키 b의 값을 조작한다고 할 때, 키 a를 조회함과 동시에 값이 생성되므로 부적절하다.

• 키의 조건에 따라 다양한 default value 지정이 필요한 경우

  • 이 경우에는, 대부분 dict의 setdefault()를 사용하는 것이 간결할 것 같다.

반면, defaultdict는 이럴 때 편리하거나 효율적이다.

• 값이나 아이템의 추가만 일어나는 경우
• 한번 조회한 키가 반드시 다시 사용되는 경우