[PYTHON] 백준 1715 - 카드 정렬하기

성능 요약

메모리: 121784 KB, 시간: 448 ms

분류

자료 구조, 그리디 알고리즘, 우선순위 큐

문제 설명

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

---

아이디어, 문제풀이

• 무조건 두개를 더한다. 로 접근하면 편하다.
• 두개를 빼서 더하고, 그 값을 다시 리스트에 푸시하는 식으로 진행
• 1개가 남을때까지 반복한뒤, 그 한개를 출력하는 방식으로 진행하는게 코드상 깔끔하다.

---

TROUBLE SHOOTING

• 가장먼저 궁금했던건, heapq.heapify() 와 리스트에 하나씩 집어넣는 for문을 활용한 heapq.heappush() 두가지로 만들어진 배열이 일치하는가? 였는데. 역시 일치했다. 수많은 예제코드들을 갈아넣으며…

  n = int(input())
  n_list = []
  for i in range(n):
      x = int(input())
      n_list.append(x)
  
  heapq.heapify(n_list)

  나는 직접 코딩하며 손으로 그리는것으로 완벽하게 이해를 했는데, 과정을 일일히 기록할수 없어 chat gpt에게 물어본 답변도 함께 첨부하곘다.

  두 코드 스니펫은 비슷하게 동작하지만, 약간의 차이가 있습니다.
  
  첫 번째 코드 스니펫에서는:
  
  1. **`n_list`**를 초기화합니다.
  2. 입력을 받아 **`n_list`**에 추가합니다.
  3. **`heapq.heapify(n_list)`**를 사용하여 **`n_list`**를 힙으로 변환합니다.
  
  두 번째 코드 스니펫에서는:
  
  1. **`n_list`**를 초기화합니다.
  2. 입력을 받으면서 동시에 **`heapq.heappush(n_list, x)`**를 사용하여 힙에 추가합니다.
  
  두 방법 모두 **`n_list`**를 힙으로 만들지만, 
  두 번째 코드 스니펫은 입력을 받으면서 힙에 추가하는 것이 더 효율적입니다.
  첫 번째 코드 스니펫에서는 리스트에 모든 값을 추가한 다음 한 번에 힙으로 변환하고 있습니다.
  
  두 번째 방법이 더 효율적인 이유는 다음과 같습니다:
  
  1. 입력을 받으면서 바로 힙에 추가하므로, 
  힙의 특성이 유지되면서 값이 추가되기 때문에 추가적인 **`heapify`** 호출이 필요하지 않습니다.
  2. 힙에 원소를 추가할 때마다 힙의 특성이 유지되므로, 
  중간 과정에서 힙을 사용하려면 두 번째 방법이 더 적합합니다.
  
  따라서 두 코드 스니펫은 비슷한 작업을 수행하지만, 
  두 번째 방법이 더 효율적이고 실제 문제 해결에 더 적합합니다.

• 구현으로 넘어가면, 처음엔 아래 코드처럼 간단한 수식 계산으로 진행했다. 그러나 내가 만든 알고리즘은 문제와 맞지 않았다. 지금은 리뷰를 하며 자신감이 붙었지만, 이 문제를 풀때에는 heapq사용이 미숙해 어떻게든 돌아가보려고 했던것 같다.

  import heapq
  import sys
  input = sys.stdin.readline
  
  n = int(input())
  n_list = []
  for i in range(n):
      x = int(input())
      n_list.append(x)
  
  heapq.heapify(n_list)
  
  print(n_list)
  
  sum_list = []
  k = sum(sum_list)
  
  for i in range(n):
      
      #sum_list의 합을 k에 저장
      # k = sum(sum_list)
  
      #배열중 최소값을 가져옴
      a = heapq.heappop()
  
      k = k + a
  
      sum_list.append(a)
  
  print(k)

• 그 외는 앞선 힙 문제들의 확장선에 있기에, 활용할줄만 안다면 쉽게 구현 가능했던 문제였다.

---

코드

#https://www.acmicpc.net/problem/1715
#카드 정렬하기
#1715

import heapq
import sys
input = sys.stdin.readline

n = int(input())
n_list = []
for i in range(n):
    x = int(input())
    heapq.heappush(n_list, x)

# print(n_list)

# sum_list = []
# k = sum(sum_list)

result = 0

# while len(n_list) > 0:
while len(n_list) > 1: #1개가 남을때까지 반복해야하만 한다. 

#이런 알고리즘을 쓴 이유는, 2개씩 더해갈것이니깐!
#두개를 더한값이 원래 있는 수들보다 작은 2개에 포함된다면 
#그것또한 먼저 계산해야한다. 제일 적은값을 뽑아내는게 맞다.
    a = heapq.heappop(n_list)
    b = heapq.heappop(n_list)

    sum = a + b
    result = result + sum

    heapq.heappush(n_list, sum)

    # print(n_list)

print(result)