[백준] 1339번. 단어 수학

[문제]

 

www.acmicpc.net/problem/1339

1339번: 단어 수학

 

[풀이]

 

입력으로 주어진 알파벳을 숫자로 바꿔서 알파벳 합의 최댓값을 구하는 문제이다.

 

먼저 해당 알파벳이 몇번째 숫자로 얼마나 나왔는지에 따라 알파벳에 대한 숫자를 지정했다.

예를 들어 ABCD라면, A->9, B->8, C->7, D->6 이렇게 큰 자릿수가 큰 숫자를 가지도록 해야 최댓값을 구할 수 있다.

 

따라서 visited 배열에 해당 알파벳의 자릿수를 저장하였다.

위의 예시로는 visited[0]=1000, visited[1] = 100, visited[2] = 10, visited[3] = 1

이와 같은 방식으로 입력으로 주어진 알파벳에 대해 저장하였다.

입력이 ABA인 경우 visited[0] = 101, visited[1] = 10이 된다.

 

이렇게  visited 배열을 저장하고, visited 배열에 저장된 값을 기준으로 정렬하였다.

그리고 9부터 시작하여 큰 값을 가지고 있는 알파벳에 할당하였다.

이런 식으로 각 알파벳에 대해 숫자를 지정하고 합을 구하여 출력하였다. 

 

[코드]

 

시간 : 0ms

 

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

int N;
vector <string> v;

int alphabet[26]={0,};
int visited[26]={0,};

int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++){
        string tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    vector <pair<int,int>> order;
    
    for(int i=0;i<N;i++){
        string str = v[i];
        int _size = str.size();
        int idx = 1;
        for(int j=_size-1;j>=0;j--){
            visited[str[j]-65] += idx;
            idx *=10;
        }
    }
    for(int i=0;i<26;i++)
        if(visited[i] != 0) order.push_back({visited[i],i});
    
    sort(order.begin(),order.end());
    
    int num=9;
    for(int i=order.size()-1 ; i>=0;i--){
        if(alphabet[order[i].second]==0){
            alphabet[order[i].second]=num;
            if(num>0)   num--;
        }
    }
    int ans =0;
    for(int i=0;i<N;i++){
        string str = v[i];
        int _size = str.size();
        int idx = 1;
        for(int j=_size-1;j>=0;j--){
            ans += alphabet[str[j]-65] * idx;
            idx *= 10;
        }
    }
    cout <<ans;
    return 0;
    
}