https://www.acmicpc.net/problem/1715
알고리즘 분류
- 그리디
- 우선순위큐
접근 아이디어
시간초과때문에 조금 고생을 한 문제이다.
사실 논리는 간단하다. 제일 작은 수 두 개끼리만 계속 더해가는 것이다.
리스트의 [0]을 구하는 것은 시간복잡도 O(N)이고, del로 데이터를 삭제하는 것도 O(N)이다. 이걸 알고 있어서 시간복잡도를 O(1)로 만들어줘서 큐 구현에 사용하는 collections모듈의 dequq객체를 활용해 해보려고 했지만 정렬할 방법을 모르겠어서 실패..
deque객체: https://docs.python.org/3/library/collections.html#deque-objects
(deque를 정확히 뭐라고 부르는지와 같은 정확한 정보가 필요할 때 공식사이트를 애용한다.)
그러다 최소값, 최대값을 계속해서 호출할때 사용하는 우선순위 큐 자료구조를 떠올렸다. 힙 자료구조로 우선순위 큐를 주로 구현한다.
파이썬에서는 heapq라는 모듈로 사용이 가능하다.
(데이터 추가,삭제시마다 자동으로 계속 최소 힙으로 만들어준다.)
소스 코드
