[BOJ/C#] 1339 단어수학

문제

문제 링크: https://www.acmicpc.net/problem/1339

해석

두 개 이상의 문자열이 주어졌을 때 각 알파벳을 겹치지 않는 0부터 9사이의 숫자 중 한가지로 바꾸어서 합을 구했을 때에 최대 값을 구해야한다.
가장 큰 자릿 수에 오는 문자들에게 큰 값을 부여하고 가장 큰 자리 수가 겹치는 경우 그 다음 자리수도 비교해야 한다.

가장 큰 비율을 차지하는 알파벳에 최대의 수를 부여해야 하기 때문에 결국 그리디 알고리즘이라는 것을 생각하는 것이 중요한 포인트이다.

문제 풀이

먼저 문자끼리의 우선순위를 정해야 한다. 그래야 문자에 적합한 숫자를 부여할 수 있다.

문자의 우선순위의 기준은

문자의 최대 자릿수

문자의 최대 자릿수가 같은 경우엔...

그 다음으로 오는 자릿수

를 확인해야 한다.

그래서 내가 생각한 방법은 문자가 가진 자릿수를 모두 구해서 저장한 Dictionary를 만드는 것이다.

예를 들어...
주어진 문자열이 CAB, ADDD, CCCB 3개 있을 경우
A는 10 + 1000 + 0 = 1010
B는 1 + 1 = 2
C는 100 + 0 + 1110 = 1210
D는 0 + 111 + 0 = 111

이렇게 Dictionary에 저장된다.

이제 우선순위를 기준으로 각 문자마다 숫자를 부여하자.
Dictionary에 저장된 우선순위를 가지고 내림차순으로 정렬해서 9부터 0까지 순서대로 다시 Dictionary에 저장한다.

그리고 다시 입력받은 문자열들에 숫자를 대입하면 답을 구할 수 있다.

코드

static void solution()
{
    List<string> numbers = new List<string>();
    Dictionary<char, int> map = new Dictionary<char, int>();

    int N = int.Parse(Console.ReadLine());
    for (int i = 0; i < N; i++)
    {
        string number = Console.ReadLine();
                
        for (int j = 0; j < number.Length; j++)
        {
            int temp = 0;
            if (map.ContainsKey(number[j]))
                temp = map[number[j]];
            else
                map[number[j]] = 0;
            temp += (int)Math.Pow(10,(number.Length - j));
            map[number[j]] = temp;
        }
        numbers.Add(number);
    }

    List<char> chars = map.Keys.ToList();
    chars.Sort((c1, c2) => map[c1] > map[c2] ? -1 : 1);
    for (int i = 0; i < chars.Count; i++)
        map[chars[i]] = 9 - i;

    int answer = 0;
    foreach (string num in numbers)
        for (int i = 0; i < num.Length; i++)
            answer += map[num[i]] * (int)Math.Pow(10,(num.Length - i-1));
    Console.WriteLine(answer);
}