https://www.acmicpc.net/problem/1339
1339번: 단어 수학
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대
www.acmicpc.net
백준 사이트의 알고리즘 분류 중, 그리드 알고리즘과 백트레킹 알고리즘에 분류되어 있는 문제입니다 !
처음 문제를 풀 때, 단순 자릿수가 큰 문자에 9부터 숫자를 넣어주는 방법으로 풀려고 했지만 반례가 존재하였고 그 후에 어려움을 좀 겪은 거 같아요 ㅠ
힌트를 얻으려고 다른 분들의 코드를 살펴봤는데 대부분의 코드들이 딕셔너리를 이용한 코드였습니다.
저는 딕셔너리 자료구조를 사용하는 것을 별로 선호하지 않아서 다른 방식으로 푼 분의 코드를 참고했어요 !
https://suri78.tistory.com/183
[백준알고리즘] 1339번: 단어 수학 -Python
[백준알고리즘] 1339번: 단어 수학 -Python https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다.
suri78.tistory.com
https://velog.io/@dding_ji/baekjoon-1339
백준 1339. 단어수학 - 문제풀이 (Python/파이썬)
🔎 1339번 단어 수학 - 문제풀이(파이썬)
velog.io
소스코드
풀이
문제의 핵심은 자릿수가 높은 알파벳이라고 무조건 높은 숫자를 부여하면 안된다는 것입니다 !
그렇게 된다면 반례가 존재하여 테스트를 제대로 통과할 수 없어요.
그렇기에 단어의 각 알파벳들이 위치한 자릿수의 합대로 높은 순서를 부여하는 방식을 선택해야 합니다.
ex)
word1 = 'ABC'
word2 = 'ADEF
'A'의 자릿수 = 10*2 + 10*3 = 1100, => 9
'D'의 자릿수 = 10*2 = 100, => 8
'B','E'의 자릿수 = 10, => 7,6
'C','F'의 자릿수 = 1 => 4,5
합 = 10839
ord() 함수는 ord('문자')로 사용되는데, 문자를 넣으면 그에 맞는 유니코드를 리턴해줍니다
ex) ord('A') = 65, ord('B') = 66
이를 통해 alphabet이라는 리스트에서 인덱스를 구분해줄 수 있습니당
이렇게 구한 alphabet이라는 리스트를 내림차순으로 정렬하면, 자릿수가 큰 알파벳부터 정렬할 수 있습니다.
이후, 자릿수가 높은 알파벳순으로 9 ~ 0 까지의 수를 부여한 뒤, 합을 구하는 ans에 계속해서 더해준다면 답을 구할 수 있습니다 !