골드는 골드구나...
확실히 실버보다 조금 까다로운듯 싶다

#1339 단어 수학

🔗https://www.acmicpc.net/problem/1339

처음 든 생각

어차피 최대의 합을 구하는 거이므로 자릿수 순서대로 큰 숫자를 배정해주면 된다고 생각했다. -> 그랬는데 오답...ㅠ_ㅠ
그래서 다시 생각해보니, 자릿수를 우선으로 고려하되 같은 자릿수일 때는 빈도 또한 고려를 해야하는 것을 깨달았다.

구현

1. 우선 a라는 딕셔너리 자료형을 하나 선언해 각 알파벳의 자릿수와 나타나는 빈도 수를 수치화 해서 정리해놓는다. (만약 BB AB라면, B는 12, A는 10!!)
2. 그걸 내림차순으로 sort하고(sorted_a) assiginment라는 딕셔너리에 sorted_a의 순서대로 큰 수를 배정한다.
3. 다시 한번 입력받은 알파벳들을 읽으며, assiginment와 비교해 수를 더해준다.

import sys
n=int(sys.stdin.readline().rstrip())
word_list = [sys.stdin.readline().rstrip() for _ in range(n)]

assignment={} #실제 알파벳에 숫자를 배정해주는 dictionary
a={} 
answer=0
max_num=9

for word in word_list: #단어를 읽으며 각 알파벳의 자릿수와 나타나는 빈도를 수치화시켜준다.
    digit=len(word)
    for alphabet in word:
        if alphabet not in a: #해당 알파벳이 기존 dictionary에 없던 거일때는 key를 추가해야함
            a[alphabet]=pow(10,digit-1)
        else: #해당 알파벳이 기존 dicitionary에 있던 거일때는 값을 더해야함
            a[alphabet]+=pow(10,digit-1)
        digit-=1

sorted_a=sorted(a.items(),reverse=True,key=lambda item:item[1]) #value값을 기준으로 내림차순으로 정렬한다.

for item in sorted_a: #알파벳에 숫자를 배정해주는 과정
    assignment[item[0]]=max_num
    max_num-=1

for word in word_list: #최종적으로 수를 더해주는 과정
    digit=len(word)
    for alphabet in word:
        answer+=assignment[alphabet]*pow(10,digit-1)
        digit-=1

print(answer)

#1715 카드 정렬

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

처음 든 생각

카드를 오름차순으로 정렬한 후 차례대로 두개씩 짝지어 더해주는 방식으로 하면 되는거 아닌가?! -> 오답 ㅠ_ㅠ
나는 너무 당연하게

10 10 20 30 40 50 60 100이 있다고 했을 때,
(10+10)
(10+10)+20
(((10+10)+20)+30
((((10+10)+20)+30)+40
...
이렇게 차례대로 가면 된다고 생각했는데,

(10+10)
(10+10)+20
(((10+10)+20)+30
((((10+10)+20)+30)+40 ←여기서부터 문제 발생!
((((10+10)+20)+30)은 70인데, 70보다 작은 50을 먼저 더해줘야하기 때문에 오답이 나온다.

구현

이게 구현 가능하려면 더해주는 매 순간마다 sort를 해줘야하는데,
내가 생각하는게 맞나? 싶어서 질문 검색을 들어가보니 많은 사람들이 heapq(우선순위큐)를 통해 구현을 했다.
굳이 sort를 하지 않아도 새로운 값을 집어 넣는 순간마다 자동으로 정렬이 되기 때문에 해당 문제에 알맞는 자료구조인 것 같다!

import sys
import heapq

n=int(sys.stdin.readline().rstrip())
h=[]
answer=0

for _ in range(n): #heapq에 카드수를 하나씩 넣어준다.
    heapq.heappush(h,int(sys.stdin.readline().rstrip()))

for _ in range(n-1): 
    tmp=heapq.heappop(h)+heapq.heappop(h) #매순간 제일 작은 두 카드수를 더해준다
    answer+=tmp
    heapq.heappush(h,tmp) #더해진 카드 수를 다시 heapq에 집어넣어준다.

print(answer)

#1744 수 묶기

🔗https://www.acmicpc.net/problem/1744

처음 든 생각

1. 양수는 큰 순서대로, 음수는 작은 순서대로 곱해줘야 제일 큰 수가 나오겠다. -> 이 둘을 나눠서 생각해야 겠구나.
2. 음수와 0이 만날 경우에는 곱해주는게 더 크다. -> 0을 음수 리스트에 넣어주자
3. 1과 1을 제외한 숫자가 만날 경우에는 더해주는게 더 크다.

구현

숫자의 개수가 홀수일때가 조금 애매했는데,
일단 리스트에서 두개씩 pop을 하며 숫자의 개수가 0개 혹은 1개가 남도록 연산을 진행한 다음
1개가 남았을때는 따로 수를 더해주었다.

import sys
n=int(sys.stdin.readline().rstrip())
answer=0
#양수 음수를 각각 저장
positive=[]
negative=[]

for _ in range(n): #수를 입력받아 따로따로 저장한다.
    num=int(sys.stdin.readline().rstrip())
    if num>0:
        positive.append(num)
    else:
        negative.append(num)

#양수는 큰수부터, 음수는 작은수부터 곱해주는게 크므로 각각 내림차순, 오름차순으로 정렬한다.
positive.sort(reverse=True)
negative.sort()

#양수
while len(positive)>1:
    a=positive.pop(0)
    b=positive.pop(0)
    if a>1 and b>1: #모두 1보다 클 경우에는 곱해준다.
        answer+=a*b
    elif a==1 or b==1: #둘 중 하나가 1일 경우에는 더해준다.
        answer+=a+b
    
if len(positive): #수의 개수가 홀수일 경우 남은 1개를 더해준다.
    answer+=positive[0]

#음수
while len(negative)>1: #0이 음수와 만나든, 음수가 음수와 만나든 곱해주는게 더 크다.
    answer+=negative.pop(0)*negative.pop(0)
if len(negative): #수의 개수가 홀수일 경우 남은 1개를 더해준다.
    answer+=negative[0]

print(answer)