무민은귀여워

[백준]1339 단어 수학 본문

IT/알고리즘

[백준]1339 단어 수학

moomini 2021. 5. 17. 23:09
반응형

https://www.acmicpc.net/problem/1339

 

1339번: 단어 수학

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대

www.acmicpc.net

 

해결방법

1. A, B, C... 를 키로, 값을 정수로 하는 맵을 준비

2. 자릿수를 가중치로 하여 해당 키값에 누적으로 저장

3. 값을 기준으로 정렬하여, 앞에서 부터 9, 8, 7... 을 부여

4. 문자열을 부여한 값으로 대치하여 계산

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
 
using namespace std;
typedef pair<char, int> ci;
 
int main()
{
    int n;
    cin >> n;
 
    vector<string> v;
    map<char, int> m;
 
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        v.push_back(str);
    }
 
    for (int i = 0; i < 26; i++)
    {
        int temp = i + 65;
        m[(char)temp] = 0;
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        string s = v[i];
        for (int j = 0; j < s.size(); j++)
        { 
            m[s[j]] = m[s[j]] + pow(10, (s.size() - j - 1));
        }
    }
 
    vector<ci> vec(m.begin(), m.end());
 
    sort(vec.begin(), vec.end(), [](ci a, ci b) {
        return a.second > b.second;
        });
 
    int num = 9;
    vector<ci> vec2;
    for (ci it : vec)
    {
        ci tci = ci(it.first, num);
        vec2.push_back(tci);
        it.second = num;
        num--;
        if (num < 0)
            num = 0;
    }
 
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        string s = v[i];
        for (int j = 0; j < s.size(); j++)
        {
            for (ci it : vec2)
            {
                if (it.first == s[j])
                {
                    result = result + it.second * pow(10, s.size() - j - 1);
                }
            }
        }
    }
 
    cout << result;
 
    return 0;
}
반응형

'IT > 알고리즘' 카테고리의 다른 글

깊이 우선 탐색, 너비 우선 탐색 구현 수도코드  (0) 2021.05.18
이진트리 순회  (0) 2021.05.18
Bubble(버블 정렬), Insertion(삽입 정렬), Quick(퀵 정렬) 소스  (0) 2019.11.27
[코딩인터뷰] 자료구조  (0) 2019.11.22
[알고스팟] 울타리 잘라내기 FENCE  (0) 2019.11.19
'IT/알고리즘' Related Articles more
Comments