https://www.acmicpc.net/problem/1339
시간 2초, 메모리 256MB
input :
- N(1 ≤ N ≤ 10)
- N개의 줄에 단어가 한 줄에 하나
- 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자
output :
- 단어의 합의 최댓값을 출력
조건 :
- GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.
와.....
난 당연히 문자열 길이가 긴 것부터 제일 앞에서 부터 이 알파벳이 이미 저장된 것인지 확인을 하며 체크 해야 하는 줄 알았다. 근데 웬걸
2
AB
BB
의 경우에는 B 부터 숫자를 집어넣어줘야 한다. 와 멘탈 날라감 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
그러고 나서 다른 분들의 풀이를 보고 와 저렇게 하는구나 싶었다.
예제의 경우도 살짝은 눈속임을 주려고 한 것이 아니였을까 싶다.
문제를 접근하는 두 가지 방법이 존재한다.
각 알파벳이 출현하는 위치를 기록하는 방법, 모든 조건을 갖춰서 기록하는 방법.
그리고 출현하는 위치를 이용하는 것이 훨씬 그냥 편해보인다 ㅋㅋㅋㅋㅋㅋ
각 알파벳이 천의자리, 백의 자리 어디에 출현하는지 확인을 하고 그 자릿수를 덧셈으로 기록해두는 것이다.
2
AAA
AAA
의 경우 100, 10, 1 의 자리 모두 출현 alpha[0] += 111
2째 줄에서도 100, 10, 1의 자리 모두 출현 alpha[0] += 111 해서
이 모든 알파벳들을 내림차순으로 정렬을 한 다음 이것들을 순서대로 *9, *8 ... 계속 해주는 것이다.
가장 영향력이 큰 알파벳부터 가장 큰 수를 가지는... 와우
import sys
alpha = [0] * 26
n = int(sys.stdin.readline())
for i in range(n):
string = sys.stdin.readline().strip()
for j in range(len(string)):
pos = len(string) - j - 1
word = ord(string[j]) - ord('A')
alpha[word] += 10 ** pos
alpha.sort(key=lambda x:-x)
ans = 0
for i in range(9, -1, -1):
ans += alpha[9 - i] * i
print(ans)
내가 만들어 놓은 코드가 좀 깔끔하지는 않긴 하지만..
현재 알파벳이 어느 위치에 있는지 확인 하기 위해 len() - 1 에 j를 빼서 확인.
아스키 코드 이용, 10의 제곱을 통한 자리 확인.
sort를 통해 내림차순 정렬 하고.
곱하는 경우에 9 일때 idx 0 / 8일 때 idx 1 딱 좋게 증가하니까 저렇게 나타냈다.
