일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
Tags
- heapq
- 프로그래머스
- Combinations
- Set
- 수학
- 그리디
- backjoon
- divmod
- 백준
- 파이썬
- 동적 계획법
- 카카오
- 위클리 챌린지
- programmers
- Zip
- 다익스트라
- lambda
- 재귀함수
- Re
- 정규식
- dfs
- java
- 이분탐색
- BFS
- python
- 추석맞이 코딩챌린지
- 자바
- KAKAO BLIND RECRUITMENT
- DateTime
- 정렬
Archives
- Today
- Total
상상쓰
[백준] 카드 정렬하기 본문
https://www.acmicpc.net/problem/1715
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
우선순위 큐(heapq) 를 이용해서 가장 작은 2개의 숫자의 합을 계산해주고 그 값을 또 queue 에 넣어준다. 이러한 과정을 반복하여 queue 에는 하나의 값만 남을 때까지 계속한다. 마지막으로 숫자의 합을 계속 더해준 answer 를 return 한다.
import sys
import heapq
answer = 0
N = int(sys.stdin.readline())
queue = []
for i in range(N):
heapq.heappush(queue, int(sys.stdin.readline()))
while len(queue) > 1:
AB = 0
for i in range(2):
AB += heapq.heappop(queue)
answer += AB
heapq.heappush(queue, AB)
print(answer)
'Coding Test' 카테고리의 다른 글
[백준] 캠핑 (0) | 2021.06.10 |
---|---|
[프로그래머스] 외벽 점검 (0) | 2021.06.09 |
[백준] 주유소 (0) | 2021.06.08 |
[프로그래머스] 수식 최대화 (0) | 2021.06.08 |
[프로그래머스] 불량 사용자 (0) | 2021.06.08 |
Comments