카드 정렬하기 (골드 4)

주어진 예시가 1개이다. 주어진 예시만 보고는 "뭐야 왜 이렇게 쉬워" 그냥 정렬만 하면 되지 않을까 했지만 골드4 문제에서 그럴 일 없다고 생각해서 몇 가지의 예시를 만들어 문제의 감을 얻었다.

10 10 10 10의 경우 주어진 예시처럼 계산한다면, 20 + 20 + 10 + 30 + 10 = 90이다.

10 10 10 10
(20) 10 10
(30) 10
(40)

하지만 (10 + 10), (10 + 10) 20, 20으로 먼저 묶고 마지막에 20 + 20을 하면 80이 된다.

10 10 10 10
(20) 10 10
20 (20)
(40)

여기서 감을 얻었는데 처음에 배열에서 가장 작은 두 수를 합치고 그 다음 갱신된 배열에서 가장 작은 두 수를 합치는 것이다.

여기서 포인트는 "잦은 min값 호출"이다. 잦은 min값 호출에서 가장 빛나는 것중 하나는 최소 힙이다.
계산마다 최솟값을 두번 pop하고, 두번 pop한 값들을 더해서 다시 배열에 넣고
또 두번 pop하고의 반복이다.

종료 조건은 heapq의 길이가 1이 될 때이다. 더해지는 계산이 이루어질 때마다 count에 연산값을 쌓아주면 된다.

from sys import stdin
import heapq

n = int(stdin.readline())

card = [int(stdin.readline()) for _ in range(n)]

card.sort()

def loof(card):
    count = 0
    while len(card) > 1:
        first = heapq.heappop(card)
        second = heapq.heappop(card)

        heapq.heappush(card, first+second)
        if len(card) < 1:
            break
        count += first + second
    return count
        
count = loof(card)
print(count)

이 문제는 현재의 선택, 즉 현재의 배열에서 가장 작은 두 수를 삭제하고 삭제한 두 수의 합을 업데이트 한다. 현재의 최적 해와 반복되서 생성될 미래의 같은 로직의 해들을 모두 더하는 것이다. 그러므로 그리디한 방식이 최적해가 될 수 있다.

단어 수학 (골드 4)

예시를 가지고 계속 생각했다. 가장 큰 자리수에 최대한 큰 한자리의 수를 배치해야한다고 생각했다. 예시를 보면 GCF + ACDEB는
A, C, D+G, E+C, B+F 이다. 순서대로 10^4... 10^0 을 곱해주면 된다. A를 함부로 9로 정할 수 있을까? 만약 10개의 알파벳조합이 모두 5개의 알파벳을 가진다면 10^4자리는 어떻게 정해야 할지 혼란스러울 것이다.

계속 생각하다보니 각 알파벳의 모든 자리에서 어떤 분포를 가지는 지 구하면 되겠구나 생각했다 알파벳 조합이 수백개라면 수백개의 알파벳의 1의 자리에서의 개수,..., 10^4의 자리에서의 개수를 모두 구한다. 그리고 각각의 개수에 자리에 맞는 10^n을 곱해주면 해당 알파벳들의 우선순위를 정할 수 있다.

예시의 경우 다음과 같다. 이제 우선순위대로 A => 9, C => 8 ... F => 3으로 바꾸어주면 된다.

from sys import stdin

from collections import defaultdict
n = int(stdin.readline())

dict_digit = {
}
for i in range(0,8):
    dict_digit[i] = []
str_full = ""
before_change = []
for i in range(n):
    str_data = str(stdin.readline().rstrip())
    before_change.append(str_data)
    str_full = str_full + str_data
    item = list(str_data)
    item.reverse()

    for idx, alpha in enumerate(item):
        dict_digit[idx].append(alpha)

unique_alpha = set(str_full)

power = defaultdict(int)
for i in unique_alpha:
    for key in dict_digit.keys():
        package = dict_digit[key]
        for p in package:
            if i == p:
                power[i] += 10 ** key

power = [(key, value) for key, value in power.items()]
power.sort(key=lambda x:-x[1])

changer = {}
num = 9
for i in power:
    changer[i[0]] = num
    num -= 1

after_change = []
for i in before_change:
    item = i
    for k in i:
        item = item.replace(k, str(changer[k]))
    after_change.append(item)


# stack
final = 0
for i in after_change:
    num = int(i)
    final += num

print(final)

문제 분류가 그리디 알고리즘인데, 그리디라는 개념이 참 추상적인 듯 하다. 정렬개념과 그리디가 거의 맞닿아 있는 듯 하다.

나의 풀이에서 그리디 개념은, 각 알파벳의 power를 정렬했을 때 가장 높은 것에 가장 높은 한자리 수를 배정하는 것이다. 이 선택이 미래에 영향을 주지 않기에 뒤를 돌아보지 않고 순서대로 숫자를 배정해줘도 상관없다. 그런 의미에서 그리디하다고 볼 수 있을 것 같다.