[Python] 백준 1339: 단어 수학

풀어본 그리디 알고리즘 문제 중에 가장 어려웠다.
나는 블로그에 못 푼 문제들만 올리기 때문에 이 문제 역시 못 풀었다.

나의 접근법은 이렇다.
Deque를 사용하여 들어오는 단어의 길이를 비교하여 가장 많은 단어부터 popleft를 하며 (9-i)만큼 숫자를 지정해주고 i를 1 더해주는 것이었다. 나름 괜찮은 방법이라고 생각했는데 구현하는 것이 너무 어려웠고, 코드를 짜다보니 말도 안되는 접근이라고 생각했다. 결국 답안을 보았다.

n = int(input())
words = [input().rstrip() for _ in range(n)]
alpha = {}
i = 0
answer = 0
for word in words:
    cnt = len(word) - 1
    for w in word:
      if w not in alpha:
          alpha[w] = 10 ** cnt
          i += 1
      else:
          alpha[w] += 10 ** cnt
      cnt -= 1

values = sorted(alpha.values(), reverse=True)
cnt = 9
for i in values:
    answer += i * cnt
    cnt -= 1
    

print(answer)

우선 핵심과정은 dictionary에 알파벳 별로 수를 넣어주는 것이다.
그냥 수가 아니라 1, 10, 100, 1000, 10000 처럼 자릿수 $10^n$을 넣어주고, 해당 자릿수의 값 자체는 출력직전에 넣어주었다.

만약 "ABCDE"가 들어왔다면 A는 만의 자리이므로 $10^4$가 들어가야한다. 그러기 위해서 "ABCDE"의 길이(5)에 1을 뺀 값을 거듭제곱해주면 된다.

만약에 "ABCAE" 처럼 A가 만의 자리에도 오고 십의 자리에도 왔을 경우에는 dictionary에 이미 들어있으므로 그 자릿수만큼 더해준다.
더해주는 이유는 다음과 같은 상황이 올 수 있기 때문이다.
AB
BB
BB

만약 이렇게 들어왔을 때 A가 9, B가 8이 들어가면 총합 274가 나온다.
하지만 A가 8, B가 9일 때에는 287로 전자보다 큰 값이 나오므로 정답이 된다. 전자의 경우에 Dictionary를 뒤져보면 {9: 10, 8: 23} 일 것이다.
이게 정답으로 되는 이유는 단어의 개수가 총 10개(1<=N<=10)이기 떄문인 것도 있다. 만약 단어의 개수가 100개라면 수의 자릿수가 더 이상 의미가 없어질 것이다.

실패 후 성장

이번 그리디 문제는 꽤 어려웠다.
약간 비슷한 접근까지는 가긴했지만 구현하는 것에 어려움을 겪었다. 백준 골드 4 문제였다. 흔히들 기업 코딩테스트가 백준 골드2 ~실버 2 정도 수준이라고들하는데 골드4도 이렇게 어려운데 골드 2는 두렵다.. 이런 문제도 풀다보면 적응되고 늘겠지?