https://www.acmicpc.net/problem/1132
알고리즘 분류
- 그리디
접근 아이디어
1339 단어수학이랑 상당히 유사한 문제이다.
처음에 똑같은 문제인 줄 알고 접근했다가 뭐가 문제지 한참 고민했다.
차이점은 0으로 시작하는 숫자는 없다 이다.
기본적인 접근법은 동일하다.
각 알파벳의 자리수를 구해줘서 가장 큰수부터 9에서 0까지 순서대로 넣어주면 되는 것이다.
ex) ABC, BCA에서 A는 100+1, B는 10+100, C는 1+10
alpha딕셔너리 {'A': [], 'B': [], 'C': [], 'D': [], 'E': [], 'F': [], 'G': [], 'H': [], 'I': [], 'J': []}에 각 알파벳의 자리값을 넣어준다.
first리스트는 입력한 알파벳들의 가장 처음 알파벳을 저장한다.
그리고 alpha딕셔너리에서 자리값을 기준으로 내림차순 정렬한다.
예를 들어 입력값을
8
A
BB
CCC
DDDD
EEEEE
FFFGGG
HHHHHHH
IJJJJJJJ
다음과 같이 주었을 때 정렬 후 alpha리스트=
[('I', [10000000]), ('H', [1111111]), ('J', [1111111]), ('F', [111000]), ('E', [11111]), ('D', [1111]), ('C', [111]), ('G', [111]), ('B', [11]), ('A', [1])]
first리스트=['A', 'B', 'C', 'D', 'E', 'F', 'H', 'I']이다.
이때, 값이 더 작은 G가 맨 앞에 온 경우가 없으므로 맨 뒤로 보내 0을 할당받게 한다.
소스 코드
