문제 - 카드 정렬하기

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

🤨풀이를 어떻게 생각했는가?

1. 문제의 조건

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

2. 고민 과정

• 문제에서 물어보는 것은 최소한 몇번의 비교가 필요할까? 이다.
• 최소라면, 매 비교 횟수가 분기마다 최소로 이루어져야 한다.
  • 그러므로, 매 비교마다 최소인 값과 비교해야 한다.
• N개의 카드 묶음의 각각의 크기가 주어진다면, 오름차순으로 정렬되어 있어야 할 것이다.
• 정렬되어 있는 것을 토대로, 위에서 말한 비교 연산을 매 분기마다 반복해주면 될 것 이다.

3. 주요 포인트

• 매 분기마다 최소인 값과 비교해야 한다.
• 매 분기마다 배열이 정렬되어 있어 즉시 최소인 값을 찾을 수 있어야 한다(시간 복잡도 때문)
  • 이 말인 즉슨, 사용하는 자료 구조 자체가 최소, 최대로 정렬되어 있으면 굳이 해줄 필요가 없다. (heap 자료구조 이용)

4. 구현 과정

1. 파이썬의 heapq는 기본적으로 Minheap으로 되어 있으므로, 우리가 원하는 조건에 최적이다. heapq를 이용해 입력 값들을 최소 heap으로 만들어 준다. #1, #2 둘 다 같은 결과값이 나온다.

import heapq

#1 기존 배열을 만들고, heap 정렬을 해주는 방식
input = sys.stdin.readline
N = int(input())
card = [int(input()) for _ in range(N)]
heapq.heapify(card)

#2 애초에 값을 heappush로 받아 Minheap을 만드는 방식 
input = sys.stdin.readline
N = int(input())
card = []
for _ in range(N):
	heapq.heappush(card, int(input())

2. 매 비교마다 결과값이 최소가 되야하기 때문에, 현재 배열에서 최솟값만을 뽑아 계산하는 반복문을 만들어 준다.

c = 0 # 이번 분기 비교한 카드의 비교 횟수
s = 0 # 총 카드 비교 횟수
while len(card) > 1:
    n1 = heapq.heappop(card)
    n2 = heapq.heappop(card)
    c = n1 + n2
    s += c
    heapq.heappush(card, c) 
    # 새로 만들어진 카드뭉치가 현재 배열에서 작은지 큰지 모르니, heappush를 이용하여 heap에 저장

3. 문제에서 원하는 출력까지 포함한 전체 코드

#전체코드# 
import heapq
import sys
input = sys.stdin.readline
N = int(input())
card = [int(input()) for _ in range(N)]
heapq.heapify(card)
c = 0
s = 0
while len(card) > 1:
    n1 = heapq.heappop(card)
    n2 = heapq.heappop(card)
    c = n1 + n2
    s += c
    heapq.heappush(card, c)

print(s)

🤔생각

• 솔직히 파이썬이 아니었다면 코드가 훨씬 길어졌을 것 같은 문제였다.
• 문제에 적힌 골드4라는 난이도에 비하면 쉬운 문제라는 생각이 들었다. 파이썬이라 그런가??