[이코테] 정렬 - 카드 정렬하기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참고하자.

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

1715번: 카드 정렬하기

사고과정

• 왜 이게 정렬 카테고리에 있는지 감이 오지 않았다.. 수열의 규칙을 찾는 것처럼 여러번 시도를 해보았지만 못 찾았다. 접두 합을 이용하는 건가 했지만 틀렸다. 풀이를 보니 핵심 포인트는 "매 상황마다 항상 작은 합을 선택하면 된다"가 최적의 해를 보장하는 것이었다.(이걸 어떻게 단번에 알지..?) 그래서 그리디 알고리즘이기도 하다.
• 매 상황마다 항상 작은 합을 선정하기 위해서 우선순위 큐(heapq 라이브러리)를 활용했다. 전혀 예상하지 못했다.
• 보통은 큐가 빌때까지 조건을 달아 while문을 빠져나왔지만, 이 문제는 큐 길이가 1일 때, 즉, 큐 안에 원소가 하나만 남았을 때 빠져나와야 한다. 왜냐하면 원소가 하나가 남았다는 것은 주어진 모든 카드의 수를 다 더했다는 것을 의미하기 때문이다.

풀이(스스로 못 푼 풀이)

import heapq

n = int(input())
array = [int(input()) for _ in range(n)]

q = []
for a in array:
    heapq.heappush(q, a)

result = 0
while len(q) != 1:
    one = heapq.heappop(q)
    two = heapq.heappop(q)
    sum_val = one + two
    result += sum_val
    heapq.heappush(q, result)

print(result)