[BaekJoon] 1339 단어수학

pyh8618·2020년 9월 26일
0
post-thumbnail

🔦 문제 링크

✍️ 나의 풀이


  • 처음에는 순열로 모든 경우의 수를 사용했지만 역시나.. 시간초과 였다
  • 내 힘으로 풀 수가 없어서 인터넷을 참고했다.
  • 그리디방식을 사용해야 한다고 한다.

<순서>

  1. 먼저 단어의 알파벳의 자릿수에 맞게 10의 제곱수를 해서 더해준다.
  2. 모든 알파벳을 정렬해 가장 값이 큰 알파벳을 구할 수 있도록 만든다.
  3. 가장 값이 큰 알파벳 부터 큰 숫자를 곱해준다.
  4. 이를 모두 더하면 최댓값을 구할 수 있다.

🛠 나의 코드


num = int(input())
word = []
for _ in range(num):
    word.append(input())

dic = {}
for w in word:
    i = 0
    for k in range(len(w)-1,-1,-1):
        if w[k] not in dic:
            dic[w[k]] = pow(10,i)
        else:
            dic[w[k]] += pow(10,i)
        i += 1

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

result = 0
k = 9
for d in dic:
    result += k*d[1]
    k -= 1
print(result)

✍️ 다른 사람 풀이


  • 딕셔너리 대신 리스트를 사용
  • 입력받은 알파벳을 'A'가 0부터 시작하는 숫자로 바꾼다.
  • 알파벳의 갯수는 26개이다.

<순서>

  1. 해당 알파벳의 자리에 맞는 10의 제곱수를 곱해준다.
  2. 값이 큰 알파벳 순서대로 정렬한다.
  3. 9 부터 큰 값에 곱해나가며 최댓값을 구한다.

🛠 다른 사람 코드


n = int(input())
word = [list(map(lambda x:ord(x)-65,input().rstrip())) for _ in range(n)]
alpha = [0] * 26 
for i in range(n):
	j = 0 
	for w in word[i][::-1]: 
    	alpha[w] += (10 ** j) 
        j += 1 				

alpha.sort(reverse=True)
ans, t = 0, 9 
for i in range(26): 
	if alpha[i] == 0: 
    	break 
    ans += (t * alpha[i]) 
    t -= 1 print(ans)

📝 정리


  • 그리드 방식 공부
  • 자릿수에 대한 문제..

🎈 참고


profile
Go Go

0개의 댓글