<문제 링크>
백준 1339번 단어 수학
문제 요약
본 문제는 대문자 알파벳으로 이루어진 영어 단어(?)의 합이 주어지고, 각 알파벳을 0~9 사이 숫자로 겹치지 않게 바꾸어 최대값을 구해야 한다.
ex0)
- 입력 : GCF + ACDEB
-> A : 9, C : 8, G : 7, D : 6, E : 5, B : 4, F : 3 으로 바꾸면 최대값 99437을 구할 수 있다.
-> 783 + 98654 = 99437 - 출력 : 99437
문제 풀이
처음에는 무작정 자릿수가 클 수록 높은 숫자로 바꿔주기만 하면 되는 줄 알았다. 그런데 이렇게 풀면 안됐었다..
(방심했다가 2시간 날렸다.)
큰 자리에 위치한 알파벳을 무작정 9로 바꿔주게 되면, 같은 알파벳이 여러 개 들어가 있는 입력의 경우, 최대값이 도출되지 않을 수 있다.
ex1)
- 입력 : ABB + BB + BB + BB + BB + BB + BB + BB + BB + BB
-> A가 가장 큰 자리인 100의 자리에 있다고 무작정 A : 9로 바꿔주게 되면 최대값이 도출되지 않는다.
| (A, B) | 수식 | 결과 |
|---|---|---|
| (9, 8) | 988 + (88*9) | 1780 |
| (8, 9) | 899 + (99*9) | 1790 |
따라서 본 문제는 각 알파벳이 숫자로 바꼈을 때, 얼만큼 자기 주장을 펼칠 수 있는지(?)를 파악해야 한다.
아래와 같이 생각해 보자.
<알파벳을 숫자로 바꾸게 되면, 다음 두 가지에 의해 크기가 결정된다>
1. 알파벳이 차지하고 있는 자릿수
-> 자릿수 크면 장땡
-> (AAAA > AAA) == (9999 > 999)
2. 같은 자릿수를 차지하고 있는 알파벳의 개수
-> 같은 자릿수에 위치한 여러 알파벳들 중, 개수가 가장 많은걸 높은 숫자로
-> 또한, 10의 자리가 10개 모이면 100의 자리가 된다.
=> 자릿수가 작아도 한 자리에서 10개가 모이면 그 다음 자릿수보다 커질 수 있다. : ex1)의 B
1, 2번을 고려해서 각 알파벳의 자기 주장(?)을 파악해야 한다.
위 개념을 토대로 각 알파벳의 자기 주장(?)을 어떻게 파악할 수 있을까?
-> 각 알파벳마다 1로 바꿔서 본인만 더한 값을 비교해 보면 된다.
위 예시 ex0)과 ex1)에 적용해 보자.
(ex0)
입력 : GCF + ACDEB
- A : 10000
- C : 1010
- G : 100
- D : 100
- E : 10
- B : 1
- F : 1
(ex1)
입력 : ABB + BB + BB + BB + BB + BB + BB + BB + BB + BB
- B : 11 * 10 = 110
- A : 100
위와 같이 각 알파벳의 자기 주장을 모두 구하고 나면 최대값은 쉽게 구할 수 있다.
그냥 자기 주장이 큰 순서대로 9 ~ 0 의 숫자를 곱하고 더해주면 정답을 구할 수 있다.
(ex0)
입력 : GCF + ACDEB
- A : 10000 * 9 = 90000
- C : 1010 * 8 = 8080
- G : 100 * 7 = 700
- D : 100 * 6 = 600
- E : 10 * 5 = 50
- B : 1 * 4 = 4
- F : 1 * 3 = 3
=> 출력 : 99437
(ex1)
입력 : ABB + BB + BB + BB + BB + BB + BB + BB + BB + BB
- B : 110 * 9
- A : 100 * 8
=> 출력 : 1790
이제 이 개념을 토대로 코드를 작성해 보자.
구현
<필자가 작성한 코드>
(더 효율적인 코드는 분명 많을 것이다.)
N = int(input())
charDic = {}
for i in range(N):
temp = list(input())
cipher = len(temp) - 1
for j in range(cipher, -1, -1):
oneChar = temp[cipher - j]
if not oneChar in charDic:
charDic[oneChar] = 10 ** j
else:
charDic[oneChar] += 10 ** j
charDic = dict(sorted(charDic.items(), key=lambda x: x[1], reverse=True))
charNum = 9
answer = 0
for c in charDic:
answer += charDic[c] * charNum
charNum -= 1
print(answer)위 코드는 아래와 같이 수행된다.
- 처음 이중 for문
-> 영어 단어를 입력받은 후, 'charDic' 딕셔너리에 각 알파벳의 자기 주장을 저장한다.- charDic = dict(sorted(~~
-> 'charDic' 딕셔너리를 value값(=자기 주장) 기준으로 정렬한다.- 마지막 for문
-> 'charDic' 딕셔너리에서 하나씩 꺼내서 9~0 순으로 곱한 후 더한다.
처음에 엄청 쉽게 봤었는데 생각보다 고민이 많이 들었던 문제였다. 좀 더 많이 풀어봐야겠다...ㅠ
