백준 1339 단어 수학

백준 1339 단어 수학 링크

• 틀린 풀이

import sys

N = int(sys.stdin.readline())

data = [[] for _ in range(11)]

saved = [] # 'ABDEF' 같은 문자열을 넣어둘 list

for _ in range(N):
    input_str = sys.stdin.readline().strip()
    list_str = list(input_str)
    saved.append(list_str) # 'ABDEF' 같은 문자열을 넣어줌

    for i in range(len(list_str)):
        k = len(list_str) - i - 1
        
        flag = True # 이미 넣은 알파벳인지 확인
        for j in range(len(data[k])):
            if data[k][j][0] == list_str[i]: # 해당 자리에 이미 넣은 알파벳이라면
                data[k][j][1] += 1 # 해당 자리에 해당 알파벳 수를 늘려줌 ex) [[], [], [], ['A', 3] => ['A',4], [], [], [],]
                flag = False
                break
        if flag: # 이미 해당 자리에 안넣은 알파벳이라면 k 번째 자리에 ['A', 1] 로 넣어줘야함
            data[k].append([list_str[i], 1])
        # if list_str[i] in data[i]:

print(data) # 결과물 ex) [[['F', 1], ['B', 1]], [['C', 1], ['E', 1]], [['G', 1], ['D', 1]], [['C', 1]], [['A', 1]], [], [], [], [], [], []]
# 그럼 아래는 이진제 가장 큰 자리 수에서 부터 있는 'A' 부터 9를 할당, 그 다음 큰 것부터 8 할당, 7할당 하는 방식
memo = dict()

available_cnt = 9
for t in range(len(data)-1, -1, -1):
    if data[t]:
        arranged = sorted(data[t], key=lambda x:x[1], reverse=True)
        
        for p in range(len(arranged)):
            try: 
                if memo[arranged[p][0]]:
                    continue
            except:
                memo[arranged[p][0]] = available_cnt
                available_cnt -= 1

answer = 0

for q in range(len(saved)):
    temp = ''
    for u in range(len(saved[q])):
        temp += str(memo[saved[q][u]])
    
    answer += int(temp)

print(answer)

예외를 생각하지 못했다.
문자열로 파악하고 가장 높은 자리수에 있는 알파벳에 큰 수를 배정하고, 같은 자리수면 해당 알파벳 갯수가 많은 것 순으로 그 다음 큰수를 배정한 다음 int로 변환 후 숫자들을 더하려했다.
헌데 이러면 다음과 같은 반례가 있다.

10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB

가장 큰 자리수인 A한테 가장 큰 수를 배정했는데 B가 역전하는 상황을 고려하지 못했다. 문자열, 자리위치가 아닌 수의 개념으로 접근해야했다 ㅠ 문자열, 자리위치로 접근하면 10이 될때 다음 자리로 넘겨줘야하는데 그럼 그 다음자리도 10이 되어 넘겨주고 그 다음도 넘겨줘야하는.. 고려해야할 상황이 많아진다.

• 다시 푼 정답풀이

import sys

N = int(sys.stdin.readline())
isinclude = [] # 이미 나왔던 알파벳인지 아닌지 확인용
data = dict() # 알파벳의 계수를 저장 및 update함

for _ in range(N):
    input_str = sys.stdin.readline().strip()
    list_str = list(input_str)

    for i in range(len(list_str)):
        k = len(list_str) - i - 1 # 자릿수 변환해줌. 가장 앞에 오는 수가 0이 아니라 가장큰 자릿수, 가장 마지막에 오는 수가 가장 낮은 자릿수
        if list_str[i] in isinclude: #이미 전에 나왔던 알파벳이면 더해주고
            data[list_str[i]] += 10 ** k
        else: # 처음 나온 알파벳이면 초기화해준다.
            isinclude.append(list_str[i])
            data[list_str[i]] = 10 ** k

result = []

for key, value in data.items(): # 정산
    result.append([key, value])

result.sort(key=lambda x: x[1], reverse=True)
answer = 0
num_top_to_bottom = 9 # 가장 많이 나온 수 부터 곱해주면서 -1 씩 감소

for t in range(len(result)): # 가장 많이 나온 알파벳부터 9부터 그 다음 알파벳은 8, 그 다음 알파벳은 7 ...  
    answer += result[t][1] * num_top_to_bottom
    num_top_to_bottom -= 1

print(answer)

자리수, 위치로 인식하는 것이 아닌 갯수로 파악했어야한다.
ex) 'ABCD'
-> 1000의 자리에 A 한 개, 100의 자리에 B 한 개, ...
[(D, 1)][(C,1)][(B,1)][(A, 1)]

가 아닌..
A가 1000개 있고, B가 100개 있고 수의 개념으로 접근해야한다.