[백준 python] 1339번 단어 수학 - 그리디

[백준 python] 1339번 단어 수학 - 그리디

레벨: 골드 4

언어: python

---

문제풀러가기

📑풀이 과정

초반에 상당히 헤매다가 질문 검색에서 힌트를 얻어서 구현하였다.
처음 아이디어는 자리수가 높은 알파벳부터 낮은 알파벳 순으로 숫자를 부여했다.
이때 문제는 아래와 같은 케이스가 들어오면 A를 9로 바꾸고 B를 8로 바꿔서 오답이 난다.

10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

이제 제대로 된 풀이를 설명하겠다.

---

자리수를 사용하면 되지만 단순히 순서만을 가지고는 풀 수 없다.
알파벳의 자리수 만큼 곱한 값을 기준으로 순서를 정해야 한다.

 

2
GCF
ACDEB

위의 예시는
A 는 만자리 10000
C 는 천자리 하나와 십의 자리 하나 1000 + 10
D 는 백자리 하나 100
G 도 백자리 하나 100
E 는 십자리 하나 10
B 는 일자리 하나 1
F 도 일자리 하나 1

 

그리고 구한 숫자가 높은 순서대로 9 ~ 0 까지 바꿔주고 모두 더해주면된다.
A 9 * 10000 
C 8 * 1010 
D 7 * 100 
G 6 * 100 
E 5 * 10 
B 4 * 1 
F 3 * 1 

위의 합은 99437
이렇게 답을 구할 수 있다.

파이썬의 딕셔너리를 이용하여 {'A' : 10000} 의 형태로 만들어주면 쉽게 할 수 있다.

📋풀이 코드

import sys

input = sys.stdin.readline

N = int(input())

dic = {}
for i in range(N):
  word = list(input().strip())

  for j in range(0, len(word)):
    alphabet = word.pop()
    if alphabet in dic:
      dic[alphabet] += 10**j
    else:
      dic[alphabet] = 10**j

dic = sorted(dic.items(), key= lambda x:x[1], reverse=True)

print(dic)

total = 0
idx = 9
for k in dic:
  total += idx*k[1]
  idx-=1

print(total)

💻 코드 라인별 풀이

  for j in range(0, len(word)):
    alphabet = word.pop()
    if alphabet in dic:
      dic[alphabet] += 10**j
    else:
      dic[alphabet] = 10**j

입력 값을 배열로 저장하고 하나씩 pop() 자리수 만큼 곱한 값을 dic에 넣어준다.
입력이 ABC 이면 ['A', 'B', 'C'] 로 배열에 넣고 pop()하여 1의 자리 부터 계산한다.

 

위 계산을 끝내면
딕셔너리에 [('A', 100), ('B', 10), ('C', 1)] 로 저장이 된다.

 

그리고 value 값으로 내림차순 정렬을 한다.

dic = sorted(dic.items(), key= lambda x:x[1], reverse=True)

total = 0
idx = 9
for k in dic:
  total += idx*k[1]
  idx-=1

각 알파벳의 값을 9부터 순서대로 곱하여 total에 저장하고 total을 출력하면 된다.

---