백준_단어수학_1339 (python)

★ 접근법

처음에 n의 최댓값은 10개이고 입력으로 주어지는 문자의 최대 길이는 8개, 구해야하는 답은 최댓값인 것을 봤을 때 모든 경우의 수를 유추하는 백트래킹, dp 마지막으로 백트래킹으로 풀 수 없을 것 같아서 그리디 알고리즘을 떠올렸다. 

 

★ 틀린 풀이법

 1. 각 문자가 등장하는 가장 큰 자릿수, 등장 횟수를 리스트로 만든다.

2. 첫 번째 값에 대해서 오름차순으로 정렬하고 두 번째 인자에대해서는 첫 번째 인자가 같다면 오름차순으로 정렬하게 했다.

3. 예제도 다 맞았고 게시판에 있는 딱 하나의 반례 빼고 모든 반례가 통과했다.

 

★ 딱 하나의 반례

10

ABB

BC

BC

BC

BC

BC

BC

BC

BC

BC

 

★ 틀린 코드

n = int(input())
data = []
dic = dict()
for i in range(n):
    text = list(input())
    for i in range(len(text)):
        if text[i] not in dic:
            dic[text[i]] = [len(text) - i, 1]
        else:
            dic[text[i]] = [max(dic[text[i]][0], len(text) - i), dic[text[i]][1] + 1]
    data.append(text) #나중에 써먹을지도 모르니 일단 data에 담아둔다.

answer = list(dic.items())
answer = sorted(answer, key = lambda x : (-x[1][0], -x[1][1]))
temp = dict()
num = 9
for i in answer:
    temp[i[0]] = str(num)
    num -= 1
total = 0

for i in data:
    tp = ""
    for j in range(len(i)):
        tp += temp[i[j]]
    total += int(tp)
print(total)

 

★ 맞은 풀이법

1. 각 문자가 등장할 때 그 자리의 가중치를 부여하는 것이다.

2. 예를 들어 십의 자리에서 등장했다면 10증가, 백의 자리에서 등장했다면 100 증가

3. 이게 끝이다 엄청 간단하다.

 

★ 맞은 코드

n = int(input())
dic = dict()
for i in range(n):
    text = input()
    for i in range(len(text)):
        if text[i] not in dic:
            dic[text[i]] = 10 ** (len(text)-1 - i)
        else:
            dic[text[i]] += 10 ** (len(text)-1 - i)

answer = list(dic.values())
answer.sort(reverse=True)
num = 9
total = 0
for i in answer:
    total += i * num
    num -= 1
print(total)

 

★ 회고

 처음에 틀리고 반례를 마주쳤을 때 가중치 시스템을 떠올렸어야 됐는데 예제가 다 맞고 대부분의 반례가 맞은 상태에서는 IF문을 추가해서 문제를 풀려고 한다. 보통 이런 상황에서는 맞는 경우가 나오기 때문에 틀린 판단이라고 생각하지 않는다. 다만, IF문을 추가해도 풀 수 없고 다른 로직인 것 같다는 낌새를 느꼈을 때는 처음에 떠올린 생각에 매몰되지 말고 유연한 사고를 하는 것도 중요한 것 같다. 화이팅이다!!!!!!!!!!!!!!!!!!!!!