[백준] 1339 : 단어 수학 - Python

문제

단어 수학.
N개의 단어 존재. 모두 알파벳 대문자.
각 대문자는 숫자로 대응되며 대응된 숫자들의 총 합이 최대가 되도록 해야한다.

내 코드

import heapq
import sys
from collections import defaultdict, deque

sys.stdin = open("input.txt", "rt")

# 단어 수학.
# n개의 단어, 각 단어 알파벳 대문자.
# 각 문자를 0~9 중 하나로 바꿔서 N개의 수를 합하는 문제.같은 알파벳은 같은 숫자로 바꿔야 함,같은 숫자 겹치면 안됨
# N개의 단어 -> 그 수의 합 최대

n = int(input())
data = []
map = defaultdict(int)
for _ in range(n):
    words = input() # 단어 입력
    data.append(words)
    for i in range(len(words)):
        now = words[i]
        map[now] += 10 ** (len(words) - i - 1)

# 값이 큰 순서대로 큰 값 부여 : value 기준
map = dict(sorted(map.items(), key = lambda x : x[1], reverse = True)) # value를 기준으로 내림차순 정렬
num_dict = defaultdict(int)
num = 9
for key, val in map.items():
    num_dict[key] = num
    num -= 1

# print(num_dict.items())
# print(data)
res = 0
for words in data:
    now = ""
    for word in words:
        now += str(num_dict[word])
    # print(now)
    res += int(now)
print(res)

• reverse=True 대신에 -x[1]로 넣어줘도 된다. (음수를 넣어줘서 내림차순 정렬로 변경)

코멘트

해당 문제는 굉장히 생각해볼 것도 많고 이후에 적용할만한 포인트가 존재.
문제 접근
각 알파벳에 숫자를 지정해줄 방법을 생각해야함.
가장 대표적으로는 하나씩 지정해서 완탐. → 불가능
서로 자릿수가 같거나 다른 알파벳을 숫자로 더해주는 과정을 거쳐간다 → 그렇다면 알파벳의 각각의 자릿수만큼 더한걸 모아보자.
각 자릿수 별로 값을 부여해서 더하는 식으로 계산했어야했음!!!

일단 그리디적으로 생각할 수 있었어야 했는데 -> 알파벳에 숫자를 할당하는 과정. 큰 숫자부터 차례대로 알파벳에 할당하면 최대의 합을 얻는다는... 최적해를 보장.

알파벳별로 자릿수 값이 나오므로 이제 값이 큰 것들부터 차례대로 9부터 넣어줬으면 됐다.

다시 생각해보면, 각 알파벳이 어떤 자리에 위치하는지에 따라 그 알파벳의 가치가 결정된다.
ex) ABC에서 A는 100의 자리 B는 10의 자리, C는 일의 자리.
따라서 각 알파벳이 어떤 자리에 몇번 등장하는지를 계싼하여 해당 알파벳의 가치를 구할 수 있다.

가치계산 :
입력 받은 단어들을 순회하면서 각 알파벳이 어떤 위치에 위치하는지를 계산하자.
A가 100의 자리 1번, 10의자리 2번 등장하면 -> 120으로 저장

알파벳에 숫자 할당:
가치가 높은 알파벳부터 큰 숫자 할당. 최종적으로 구한 값들을 value를 기준으로 정렬해서 값을 부여하면 된다.

java로 푼 코드 - HashMap 정렬 확인

import java.io.*;
import java.util.*;



public class Main {

    static int n;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static List<String> data = new ArrayList<>();
    static Map<Character, Integer> map = new HashMap();
    static Map<Character, Integer> num_map = new HashMap<>();

    static String[] words;
    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());
        words = new String[n];
        for (int i = 0; i < n; i++) {
            String data = br.readLine();
            words[i] = data;
            for (int j = 0; j < data.length(); j++) {
                char c = data.charAt(j); // ! 변환
//                System.out.println(Math.pow(10, data.length() - j - 1));
                map.put(c, map.getOrDefault(c, 0) + (int) Math.pow(10, data.length() - j - 1));
            }
        }
//        System.out.println("끝나고확인 : " + map);
        // ! 알파벳의 가치를 기준으로 내림차순 정렬
        // ! List로 정렬 후 사용
//        List<Character> chars = new ArrayList<>(map.keySet());
//        Collections.sort(chars, (a, b) -> map.get(b) - map.get(a));
        // ! Collections.sort를 통해 List형태로 Map 가져오기
        List<Map.Entry<Character, Integer>> entryList = new ArrayList<>(map.entrySet());
        // ! 이 entrySet을 정렬하는 방법 사용
        // ! entry의 값을 기준으로 내림차순 정렬 진행.
        Collections.sort(entryList, (a, b) -> b.getValue() - a.getValue());
        // ! 알파벳에 숫자 할당
        int num = 9;
//        for (char c : chars) {
//            num_map.put(c, num);
//            num -= 1;
//        }
        for (Map.Entry<Character, Integer> entry : entryList) {
            num_map.put(entry.getKey(), num);
            num -= 1;
        }
        // ! 정렬된 entryList를 순회하면서 각 엔트리의 키를 사용하여 num_map에 알파벳 숫자를 매핑
//        System.out.println(num_map);
        // ! 최종 결과
        int res = 0;
        for (String word : words) {
            int value = 0;
            for (char c : word.toCharArray()) {
                value = value * 10 + num_map.get(c);
            }
            res += value;
        }
//        System.out.println(map);
//        System.out.println(num_map);
        System.out.println(res);
    }
}