[C++/백준] 1339번: 단어 수학

문제 링크

1339번: 단어 수학

 

풀이

그리디를 사용하는 문제
처음엔 그냥 순서대로 점수 넣으려다 ACA BBD 같은 반례가 생각나서 우선순위? 느낌으로 변경함

1. 문제를 입력받으며 가장 긴 문자열의 길이를 구해준다. maxLen
2. 각 단어마다 알파벳의 우선순위를 구해주는데, ABC라는 단어가 있음면 A=100, B=10, C=1이 되게 구해준다.
3. 그러면 각 알파벳마다 우선순위가 구해지는데, map으로 되어있기 때문에 vector로 바꿔주어 value기준 내림차순 정렬을 해준다.
4. 우선순위가 높은 알파벳부터 9를 배정해주고 값을 하나씩 줄이며 숫자를 대응해준다.
5. 다시 단어를 돌면서 대응한 숫자를 넣고 answer에 더해준다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
using namespace std;

bool compare(pair<char, int> a, pair<char, int> b)
{
    if (a.second > b.second) return true;
    else return false;
}

void calcPriority(string s, int maxLen, map<char, int> &m)
{
    for (int i = 0; i < s.size(); i++)
    {
        m[s[i]] += pow(10, maxLen - (i + maxLen - s.size()) - 1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<string> arr(n);
    int maxLen = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        maxLen = max(maxLen, (int)arr[i].size());
    }

    map<char, int> priority;
    for (int i = 0; i < n; i++) // 우선순위 계산
    {
        calcPriority(arr[i], maxLen, priority);
    }

    vector<pair<char, int>> tmp(priority.begin(), priority.end()); // 우선순위로 정렬
    sort(tmp.begin(), tmp.end(), compare);

    map<char, int> hash;
    int num = 9;
    for (auto u : tmp) // 알파벳에 숫자 대응
    {
        hash[u.first] = num;
        num--;
    }

    int answer = 0;
    for (int i = 0; i < n; i++)
    {
        string str = "";
        for (int j = 0; j < arr[i].size(); j++)
        {
            str += to_string(hash[arr[i][j]]);
        }
        answer += stoi(str);
    }
    cout << answer;
}