[Python] 백준, 1339 (그리디)

 

 

 

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

1339번: 단어 수학

 

개요

- 순간순간 최선의 선택을 한다는 그리디 알고리즘 원리에 입각해 알파벳의 입장과 숫자의 입장으로 나눠 생각

- 가장 헷갈렸던 부분은 맨 앞자리에 위치한 알파벳이 같은 수준(등장하지 않았으며 자릿수가 같은)일 경우에 숫자 배분을 어떻게 해줘야하는지에 대한 고민

 

해결 방법

- 위에 서술한 두번째 고민은 큰 의미가 없었는데, 중요한 건 어떤 알파벳이 어떤 숫자를 가져가느냐가 아님

- 그것보다 얼마나 중복되어서 사용됐는지, 얼마나 앞에 나왔는지를 "숫자"의 형태로 표현하는 것이 중요

- 이를테면 ABAC + AAA 의 수식은 A: 1121, B: 100, C: 1의 형태를 갖기 때문에 9부터 차례대로 곱하여 더해주기만 하면 됨

 

코드

import sys

n = int(sys.stdin.readline().rstrip('\n'))
inputList = []
alphaDic = {}

for _ in range(n):
    new_input = list(map(str, sys.stdin.readline().rstrip('\n')))
    inputList.append(new_input)

for l in inputList:
    lengthInput = len(l)
    for i in range(lengthInput):
        if l[i] in alphaDic:
            alphaDic[l[i]] += 10 ** (lengthInput - 1 - i)
        else :
            alphaDic[l[i]] = 10 ** (lengthInput - 1 -i)

sortedAlphaList = sorted(alphaDic.items(), key=lambda item: item[1], reverse=True)

result = 0
calcuFlag = 9

for i in (range(len(sortedAlphaList))):
    result += calcuFlag * sortedAlphaList[i][1]
    calcuFlag -= 1

print(result)

 

개선할 여지

- 문제에 명시된 것은 알파벳 10개가 최대라고 주어졌는데, 이를 자의적으로 해석함 (무작위로 주어지는 알파벳의 경우 고려 x)

- in 메서드는 효율이 좋지 않은 것으로 알고 있는데, 이중 for문과 더불어 코드의 무게감을 두 배로 무겁게 동작시킴

import sys

n = int(sys.stdin.readline().rstrip('\n'))
alphaDic = {}

for _ in range(n):
    newInput = list(map(str, sys.stdin.readline().rstrip('\n')))
    lengthInput = len(newInput)
    for i in range(lengthInput):
        if newInput[i] in alphaDic:
            alphaDic[newInput[i]] += 10 ** (lengthInput - 1 - i)
        else :
            alphaDic[newInput[i]] = 10 ** (lengthInput - 1 -i)

sortedAlphaList = sorted(alphaDic.items(), key=lambda item: item[1], reverse=True)

result, i = 0, 0
calcuFlag = 9

for i in range(len(sortedAlphaList)):
    n = sortedAlphaList[i][1]
    if n == 0:
        break
    result += calcuFlag * n
    calcuFlag -= 1
    i+=1

print(result)

- 이중 for문을 도는 조건문이라도 줄여보고자 과정을 하나로 합쳤다. 사실 인풋 개수의 최대치가 그렇게 높지 않아 코드를 간결하게 가져가는 것이 크게 의미가 있어보이진 않는다.