백준(BOJ) 1132 합(Python)

문제 내용

뻔한 그리디 문제였다.

솔직히 그리디에 굉장히 자신이 없어서 그냥 다른 거 풀까 싶었는데, 취약점을 보완하기로 목표를 잡았기 때문에 그냥 도전했다.

해결 방법은 간단하다.

ABC=100A+10B+C

BCA=100B+10C+A

ABC+BCA=101A+110B+11C

이런 식으로 입력값을 모두 정리한 다음, 계수가 낮은 순으로 수를 배정한다.

합이 최대가 되어야 하므로 가장 많이 등장하는 알파벳 순으로 큰 수를 배정한다면 자연스럽게 합이 가장 커지는 구조이다.

계수를 구한 다음 정렬할 때는 최소 힙을 사용했다. 사실 그냥 리스트에서 sort()하면 될 것 같은데 이런저런 자료구조를 끌어다 쓰면서 익숙해지려고 겉멋 좀 부렸다.

수를 배정할 때는 먼저 0이 될 수 있는 알파벳인가를 먼저 확인해 가능하다면 0을 먼저 배정하고, flag를 써서 0을 배정했다면 그 다음부터는 0을 배정하지 않는다. 그 후에는 1부터 9까지 작은 순서대로 수를 배정하면 된다.

​

코드는 다음과 같다.

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n=int(input())
D={'A':0,'B':0,'C':0,'D':0,'E':0,'F':0,'G':0,'H':0,'I':0,'J':0}
hashing={'A':0,'B':0,'C':0,'D':0,'E':0,'F':0,'G':0,'H':0,'I':0,'J':0}
can_zero={'A':1,'B':1,'C':1,'D':1,'E':1,'F':1,'G':1,'H':1,'I':1,'J':1}
for i in range(n):
    x=input()
    can_zero[x[0]]=0
    k=len(x)
    for j in range(k):
        D[x[j]]+=10**(k-j-1)
L=[]
for i in D.keys():
    heapq.heappush(L,[D[i],i])
k=1
z_flag=1
for i in range(10):
    a,b=heapq.heappop(L)
    if can_zero[b] and z_flag:
        hashing[b]=0
        z_flag=0
    else:
        hashing[b]=k
        k+=1
ans=0
for i in D.keys():
    ans+=D[i]*hashing[i]
print(ans)

짜고 보니 코드가 굉장히 더럽다.

딕셔너리로 해싱도 덕지덕지 돼있고 불필요한 반복도 있는 것 같고 썩 만족스럽진 않다.

그리디를 공부할 때는 문제를 풀어보고 다른 사람들은 어떻게 풀었는 지를 확인해보는게 중요하다고 생각한다.

문제를 풀고 나서 다른 사람들 코드도 들여다보는데, 우선 내가 생각한 방법이랑 크게 다르진 않았다.

차이점이라면 나는 낮은 계수부터 처리했는데 대부분은 높은 계수부터 처리했다는 점?

나는 0을 처리하기 쉽도록 할려고 일부러 낮은 계수부터 했는데, 높은 계수부터 하면 뭐가 더 좋을 지는 잘 모르겠다.

다른 사람 코드 보는게 여간 쉬운 일이 아닌 것 같다. 의도 파악하고 코드 이해하고 하는게 어려운 것 같다.

더 연습해야겠다.