백준 1339 - 단어 수학

 

https://www.acmicpc.net/problem/1339

1339번: 단어 수학

 

그리디로 찾아가면서 푸는 문제이다. 

최대 10개와 문자 길이는 8이 최대이므로 전체를 다 돌려봐도 되고, 긴 순서대로 정해주면서 아래로 내려가면 될거라 생각했다. 

 

1)  1차 코딩

dictionry에 값을 저장해두고, 계산하는 방법이다. 

2차원 배열을 열로 돌면서 Dict에 값을 저장하고, 이미 나온 값은 Dic에서 가져오는 방법이다. 

결과는 실패

코드

arr = [['.' for i in range(8)] for i in range(10)]

num_arr = [[] for i in range(10)]

t_case = int(input())

for i in range(t_case):
    a = list((sys.stdin.readline().rstrip()))
    arr[i][8-len(a):] = a


dic = dict()

cur = 9
for i in range(len(arr[i])):
    for j in range(len(arr)):
        if (arr[j][i] != '.'):
            if arr[j][i] in dic:
                num_arr[j].append(str(dic[arr[j][i]]))
            else:
                num_arr[j].append(str(cur))
                dic[arr[j][i]] = cur
                cur -= 1

sum = 0
for item in num_arr:
    if item:
        sum += int("".join(item))
print(sum)

어디서 틀렸을까? 

--> 2차 코딩을 한 후에 Dictionary를 이용해서 다시 풀어봤다. 

짧게 코딩하는것도 좋은데, 난 이게 왜 더 잘 이해가 될까?

arr = ['.'] * 8

t_case = int(input())
num_dict = dict()

for i in range(t_case):
    a = list((sys.stdin.readline().rstrip()))
    arr[8-len(a):] = a

    for idx, value in enumerate(arr):
        if value != '.':
            if value in num_dict:
                num_dict[value] += 10 ** (len(arr) - idx - 1)
            else:
                num_dict[value] = 10 ** (len(arr) - idx - 1)

        # 계산 끝난 후 클리어
    arr = ['.'] * 8

sorted_dict = sorted(num_dict.items(), key=lambda item: item[1], reverse=True)

cnt = 9
sum = 0
for key, value in sorted_dict:
    sum += (value * cnt)
    cnt -= 1
print(sum)

 

2) 2차 코딩

이번에는 입력한 단어의 횟수와 자리를 기록을 하자 

예를 들어서, ACDEB와 GCF를 보자

ACDEB의 전체 길이는 5이다

A일때, 10 ** (len('ACDEB') - 1 - i) => 10000

C일때, 10 ** (len('ACDEB') - 1 - i) => 1000

D일때, 10 ** (len('ACDEB') - 1 - i) => 100

E일때, 10 ** (len('ACDEB') - 1 - i) => 10

B일때, 10 ** (len('ACDEB') - 1 - i)  => 1

 

for i in range(lne(arr)):
	10 ** (len(arr) - 1 - i)

 

즉 현재 몇번째 자리를 알면 10의 배수로 기록하는 것이다. 

알파벳의 전체를 배열로 두고, 문자를 돌면서 값을 계속 더하는 방법이다. 

 

결국 ACDEB와 GCF를 모두 돌려보면 아래 배열이 만들어진다.

[10000, 1, 1010, 100, 10, 1, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

이걸 값으로 내림차순으로 정렬하고, 9부터 곱해주면 된다. 

arr = [[] for i in range(10)]

num_arr = [0 for i in range(26)]

t_case = int(input())

for i in range(t_case):
    a = list((sys.stdin.readline().rstrip()))

    for i in range(len(a)):
        num_arr[ord(a[i]) - 65] += (pow(10, len(a) - i-1))


print(num_arr)
num_arr.sort(reverse=True)


sum = 0
cnt = 9
for i in num_arr:
    sum += (i * cnt)
    cnt -= 1

print(sum)