(C++) - 백준(BOJ) 1339번 : 단어 수학

www.acmicpc.net/problem/1339

1339번: 단어 수학

greedy문제였습니다.

 

풀이방법

 1. 모든 단어를 확인합니다. 매 단어마다 각 글자의 자릿수를 확인해 1의 자리라면 나온 알파벳의 가중치는 1이고 10의 자리라면 10, 100의 자리라면 100을 부여합니다. 이렇게 모든 알파벳별로 부여된 가중치의 값은 cost배열에 저장됩니다.

 

 2. 해당 가중치와 알파벳이 저장된 cost배열을 보며 pair<int,char>형태의 vector변수 v에 push해준 뒤 가중치가 큰 순으로 알파벳이 오도록 sort해줍니다.

 

 3. map 변수인 priority에 정렬된 v의 알파벳을 보며 가중치를 9부터 0까지 부여합니다.

 

 4. 부여된 가중치에 따라 단어를 수로 변환한 뒤 합산해줍니다. int 범위를 넘을 수 있으니 sum을 long long형으로 선언해줍니다.

 

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
string word[11];
int cost[26];
vector <pair<int,char>> v;
map <char,int> priority;
int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> word[i];
    for(int i = 0; i < n; i++){
        int w = 1;
        for(int j = word[i].size() - 1; j >= 0; j--){
            cost[word[i][j] - 'A'] += w;
            w *= 10;
        }
    }    

    for(int i = 0; i < 26; i++) 
        if(cost[i]) 
            v.push_back({cost[i],i+'A'});

    sort(v.rbegin(),v.rend());

    for(int i = 0; i < v.size(); i++) {
        priority[v[i].second] = 9 - i;
    }

    ll sum = 0;
    for(int i = 0; i < n; i++){
        int cnt = 1;
        for(int j = word[i].size() - 1; j >= 0; j--){
            sum += priority[word[i][j]] * cnt;
            cnt *= 10;
        }
    }
    
    cout << sum << '\n';
}