[Baekjoon, python] 1715번 : 카드 정렬하기

도입

백준 알고리즘 분류-그리디 알고리즘 열 다섯 번째 문제이다.

백준 1715번 문제, 입력, 출력

---

백준 1715번 입출력 예제 1

---

그리디 알고리즘

 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 

 

 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리.

        - 2. 최적 해 보장 불가 

        - 3. 효율성 개선

 

그리디 알고리즘 예시 : 거스름돈 최소 동전 수

그리디 알고리즘 수행절차

 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택

                현재 상태 최적화 기준 만족 여부 확인

 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인

                      현재 집합이 해가 될 가능성 검사

 3. 해 검증 : 신규 구성 집합이 해인지 검사

                문제가 아니면 1번으로 돌아가서 반복

---

풀이

1. 일단 카드 묶음의 개수(var_N)이 1이면 비교할 것이 없기 때문에 0을 출력한다.

 

2. 묶음들 중에 가장 작은 묶음 2개를 더해가면 최소 비교횟수를 구할 수 있다. 그래서 오름차순으로 sorting하여 이전의 총 비교횟수에 다음 값을 더하는 식으로 작성할 수 있다.

 

3. 우선순위 큐를 이용해서 메모리 초과를 관리한다.

---

코드

from sys import stdin
from heapq import heappush, heappop

var_N = int(stdin.readline())  # 1 <= N <= 100000

cards = []

for _ in range(var_N):
    heappush(cards, int(stdin.readline()))

if var_N == 1: 
    print(0)
else:
    rtn_sum = 0
    while len(cards) > 1: 
        min_fst = heappop(cards) 
        min_sec = heappop(cards) 
        rtn_sum += min_fst + min_sec 
        heappush(cards, min_fst + min_sec)
    
    print(rtn_sum)

---

시행 착오

1. 출력 초과

 처음에 단순히 "응? 이전값에 2배해서 다음값 더해주면 되잖아?" (참 위험한 생각.) 해서 아래 처럼 짰다. 하지만, '출력초과'를 볼 수 있었다. 반례가 있나보다...

from sys import stdin

var_N = int(stdin.readline())  # 1 <= N <= 100000
cards = []
rtn_sum = 0

for _ in range(var_N):
    cards.append(int(stdin.readline()))

cards.sort()

min_sum = cards[0] + cards[1]
rtn_sum = min_sum

if var_N == 1:
    print(0)
else:
    for i in range(var_N-2):
        rtn_sum = rtn_sum*2 + cards[i+2]
    print(rtn_sum)

2. 메모리 초과

 그래서 문제에서 처럼 알고리즘을 바꿔서 제출. 하지만, 메모리 초과...배열의 최대 크기가 100000, 여기서 sort()를 돌리면 어마어마한 오버헤드가 발생을 하는 것 같다. 그래서 다른 자료구조를 채택했는데, 그게 바로 지금 답인 '우선순위 큐'였다.

import sys

var_N = int(sys.stdin.readline()) # 1 <= N <= 100000
cards = []
for _ in range(var_N):
    cards.append(int(sys.stdin.readline())) 

cards.sort()

rtn_sum = 0
if var_N == 1:
    print(0)
else:
    for i in range(var_N-1):
        rtn_sum += cards[i] + cards[i+1]
        cards[i+1] = rtn_sum
    print(rtn_sum)

---

마무리

 알고리즘은 어렵지 않은데, 자료구조적으로 어떤 것을 채택하느냐에 따라 다른 결과를 얻었다. 시니어 레벨로 갈수록 이런 결정을 잘 하는 것이 하나의 서비스 또는 시스템을 만들 때 매우 중요하다.