1️⃣ 서론
백준 문제 1339번 단어 수학 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣ 문제 설명
이 문제는 주어진 단어의 최대 합을 구하는 문제입니다.
각각의 알파벳에 어떤 수를 넣어야 최대 합이 되고 그 최대합은 무엇인지를 출력하면 되는 문제입니다.
3️⃣ 풀이
이 문제는 처음에 브루트포스로 풀려했으나 파이썬으로 계속 시간초과가 나서 그리디로 해결하였습니다.
먼저 단어를 아스키코드A값인 65를 빼서 각 단어를 숫자로 표현합니다.
그 후 단어의 자릿수 별로 10을 곱해 숫자의 크기를 나타냅니다.
예를 들어 단어가 AAA 가 있다면 A배열에는 111이 들어갑니다.
또 다른 예로 BABBB 가 있다면 A는 1000이 들어가게되고 B에는 10111이 들어가게 됩니다.
이렇게 숫자 크기로 정렬을 한 후에 9부터 숫자를 매깁니다. 그리고 해당 숫자를 곱해주면 최대 합을 이끌어낼 수 있습니다.
그럼 소스코드를 보겠습니다.
4️⃣ 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
# 정렬된 알파벳 배열을 9부터 숫자를 매기며 최대합에 더해준다.
for i in range(26):
if alpha[i] == 0:
break
ans += (t * alpha[i])
t -= 1
print(ans)
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
