# [이.취.코] [백준] Chap 14. 정렬 - Q26. 카드 정렬하기

- Author: @mildsalmon
- Published: 2021-10-07
- Updated: 2021-10-07
- Source: http://blex.me/@mildsalmon/%EC%9D%B4%EC%B7%A8%EC%BD%94-%EB%B0%B1%EC%A4%80-chap-14-%EC%A0%95%EB%A0%AC-q26-%EC%B9%B4%EB%93%9C-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0
- Tags: 파이썬, 알고리즘, 한빛미디어, 나동빈, 코딩테스트, 문제

---

# 1. 카드 정렬하기

- 난이도
	- 중
- 풀이 시간
	- 30분
- 시간 제한
	- 2초
- 메모리 제한
	- 128 MB
- 출처
	- [1715번: 카드 정렬하기 (acmicpc.net)](https://www.acmicpc.net/problem/1715)

### A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

### B. 💡 내 답안

##### a. 😅 1차 시도 (실패)

```python

n = int(input())

array = []

for i in range(n):
    array.append(int(input()))

array.sort()
answer = array[0] + array[1]

for i in range(2, n):
    answer = 2 * answer + array[i]
    array.append(answer)
    array.sort()

print(answer)

```

##### b. 😊 2차 시도 (성공)

```python

import heapq

n = int(input())

array = []

for i in range(n):
    temp = int(input())

    heapq.heappush(array, temp)

sum_a = 0

while array:
    if len(array) == 1:
        # sum_a += heapq.heappop(array)
        break
    else:
        x = heapq.heappop(array)
        y = heapq.heappop(array)

        result = x + y
        sum_a += result
        heapq.heappush(array, result)

print(sum_a)

```

##### a. 🙄 회고

> 내 풀이

- 주어진 카드 묶음의 크기를 정렬하고 계산하였다.
	- 앞부분 (x, y, z, a) 중에서 (x, y) 부분에서 계산한 값(A)을 뒤(A, z)에서 다시 계산해주는 것을 보고 앞에서 계산한 값(A)을 2배 시켜주고 (z)를 더했다.
- 이 문제는 최솟값 2개를 더하는 것을 반복하면 되는 문제다.

> 반성

- 앞부분(x, y)를 더한 값이 (z) 혹은 (a)보다 클 수 있다는 점을 고려하지 못했다.

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

- (x, y)를 계산하고 기존 값의 리스트에 넣은 후 정렬을 반복하면 된다.
	- 다만, 파이썬 정렬 알고리즘의 시간 복잡도가 O(nlogn)이라서 시간초과가 발생한다.
- 따라서 동일한 기능을 하는 최소힙을 사용하면 된다.

##### a. 책 답안

[python-for-coding-test/4.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/14/4.py)

# 참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[2] [baekjoon](https://www.acmicpc.net/user/baekjoon). [1715번: 카드 정렬하기 (acmicpc.net)](https://www.acmicpc.net/problem/1715). Baekjoon. (accessed Oct 8, 2021)