[ 백준 1339 ] 단어 수학 - Python

문제 보기

[사용한 알고리즘]

그리디

 

[문제 접근]

주어진 단어들의 각 알파벳들의 가치를 계산한 후에 숫자를 대입하고자 하였습니다.

 

[알고리즘]

1. 알파벳의 가치를 계산합니다. 예를 들어서 1의 자리 숫자이면 + 1, 10의 자리 숫자이면 + 10을 더해 각 알파벳들의 가치를 정수로 표현합니다.

2. 가치가 가장 높은 알파벳부터 숫자를 대입합니다.

3. 모든 단어들의 합을 계산한 후 출력합니다.

 

[주의할 점]

처음에는 가중치가 아니라 가장 앞에 있는 알파벳부터 숫자를 대입하고자 하였습니다. 하지만 가장 앞에 있는 숫자부터 대입하면 예외가 발생합니다. 예를 들어서 ABB + BB + BB + BB + BB + BB + BB의 경우 A에 9, B에 8을 대입하는 것이 아니라 A에 8, B에 9를 대입하는 것이 정답입니다. 따라서 알파벳의 모든 위치를 고려한 가중치를 계산하고 숫자를 대입하였습니다.

 

[코드]

if __name__ == "__main__":
    n = int(input())  # 단어의 개수
    word = [list(input().strip()) for _ in range(n)]  # 단어 입력

    v = dict()  # 각 알파벳의 가치 계산
    visited = set()
    for i in range(len(word)):
        for j in range(len(word[i])):
            if word[i][j] not in visited:
                v[word[i][j]] = pow(10, (len(word[i]) - j - 1))
                visited.add(word[i][j])
            else:
                v[word[i][j]] += pow(10, (len(word[i]) - j - 1))

    # 가치가 높은 수부터 값 대입
    value = []
    for key in v.keys():
        value.append([v[key], key])

    # 가치순으로 내림차순 정렬
    value.sort(reverse=True)

    selected = dict()
    d = 9
    for i in range(len(value)):
        selected[value[i][1]] = d
        d -= 1

    # word 숫자로 변환
    for i in range(len(word)):
        for j in range(len(word[i])):
            word[i][j] = selected[word[i][j]]

    result = 0
    for i in range(len(word)):
        result += int("".join(map(str, word[i])))
    print(result)