[백준알고리즘] 1339번: 단어 수학 -Python

[백준알고리즘] 1339번: 단어 수학 -Python

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

1339번: 단어 수학

처음에는 DFS처럼 거의 완전탐색처럼 푸는 것 같다. 알고리즘 분류만 봐도 백트래킹으로 나와있다.

하지만 백트래킹으로 풀었을 때, 시간 초과가 발생했으며 시간을 줄이는 방법이 마땅치 않다. 실제로 다른 분들의 코드를 봐도 백트래킹처럼 푼 풀이는 보지 못했다. (보지 못했을 수도 있다.)

 

문제를 푼 방식은 오히려 그리디 방식으로 보는 것이 맞을 것 같다.

 

입력받은 각 단어들이 위치한 자릿수를 각 알파벳마다 기록해준다.

예를 들어, ABC = A*100 + B*10 + C*1이다.

그럼 alphabet[A] = 100, alphabet[B] = 10, alphabet[C] = 1 이 되는 것이다.

 

이런 식으로 ABC + BCA를 한다고 해보자. 그러면 alphabet리스트의 A, B, C의 값은 다음과 같을 것이다.

alphabet[A] = 101

alphabet[B] = 110

alphabet[C] = 11

 

이 값들을 내림차순으로 정렬해준 다음, 큰 값부터 작은 값으로 9부터 0까지 맵핑시켜주면 최댓값을 구할 수 있다.

따라서 9*110 + 8*101 + 7*11 = 1875라는 최댓값을 얻게 된다.

 

이러한 방식으로, 가장 큰 자릿수들에 위치한 알파벳부터 차례대로 9부터 맵핑시켜주는 그리디 방식으로 풀어야 시간 내에 통과할 수 있어 보인다.

n = int(input())
word = [list(map(lambda x: ord(x)-65, input().rstrip())) for _ in range(n)]
alpha = [0] * 26

for i in range(n):
    j = 0
    for w in word[i][::-1]:
        alpha[w] += (10 ** j)
        j += 1

alpha.sort(reverse=True)
ans, t = 0, 9
for i in range(26):
    if alpha[i] == 0:
        break
    ans += (t * alpha[i])
    t -= 1

print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다