백준 1339 - 단어 수학 (c++)

백준 1339 - 단어 수학

문제 링크

접근 및 생각

잘못된 접근

• 처음에 들어온 문자열을 문자로 쪼개서 문자들을 sort해서 next_permutation을 돌렸다. 돌리면서 한 문자에 어떤 숫자가 들어가는 지 결정하고, 또 문자열을 쪼개서 다 합한 것을 계산했다. 뭐라 설명해야할 지 모르겠고, 그냥 미친 짓이였다.

올바른 접근

• 받은 스트링이 ABCDE가 있다면, 이를 10000 * A + 1000 * B + 100 * C + 10 * D + 1 * E처럼 해석 하는 것이다.
  • 나는 map<char, int> m을 선언해서 char에는 문자를, int에는 숫자를 넣어줬다.
• map에 다 넣은 뒤, map의 int 기준으로 내림차순 정렬을 하려고 했다. 그래서 새 구조체를 선언했고, map을 vector로 변환하는 과정을 거쳤다.

    // 구조체
    struct Le{
        char letter;
        int value;
        Le(char a, int b){
            letter = a;
            value = b;
        }
        bool operator < (const Le & b) const {
            return value > b.value;
        }
    };

    // 벡터로 변환하는 과정
    for(auto & i : m){
        if(i.second != 0){
            exist.push_back(Le(i.first, i.second));
        }
    }

• 내림차순 정렬을 하고, 정렬한 원소 순서대로 9, 8, 7, ...을 넣어서 계산해주면 된다.

    int cnt = 9;
    sort(exist.begin(), exist.end());
    for(auto i : exist){
        answer += (cnt * i.value);
        cnt--;
    }

코드

#include <bits/stdc++.h>
using namespace std;

struct Le{
    char letter;
    int value;
    Le(char a, int b){
        letter = a;
        value = b;
    }
    bool operator < (const Le & b) const {
        return value > b.value;
    }
};

int n, answer;
string temp;
map<char, int> m;
vector<Le> exist;

int main(){
    ios_base::sync_with_stdio(false);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> temp;
        for(int i = 0; i < temp.length(); i++){
            m[temp[i]] += pow(10, temp.length() - i - 1);
        }
    }

    for(auto & i : m){
        if(i.second != 0){
            exist.push_back(Le(i.first, i.second));
        }
    }

    int cnt = 9;
    sort(exist.begin(), exist.end());
    for(auto i : exist){
        answer += (cnt * i.value);
        cnt--;
    }

    cout << answer;
}

채점 결과