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

1. 카드 정렬하기

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

A. 📜 문제

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

B. 💡 내 답안

a. 😅 1차 시도 (실패)

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차 시도 (성공)

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)

참고문헌

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

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