[BOJ] 1339 - 단어 수학

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

1339번: 단어 수학

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

bool desc(int a, int b){
    return a > b;
}

int alpha[26] = {0, };

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<string> v;
    for(int i = 0; i < n; i++){
        string str;
        cin >> str;
        v.push_back(str);
    }

    for(string x: v){
        for(int i = 0; i < x.length(); i++){
            int digit = x.length() - i;
            int value = 1;
            for(int j = 0; j < digit - 1; j++){
                value *= 10; 
            }
            alpha[x[i] - 'A'] += value;
        }
    }

    sort(alpha, alpha + 26, desc);

    int num = 9;
    int sum = 0;
    int i = 0;
    while(alpha[i] != 0){
        sum += alpha[i] * num;
        num --;
        i++;
    }
    cout << sum;
}

이 문제를 처음 봤을 때 가장 생각한 접근 방법은 문자열 길이가 긴 순서로 정렬한 뒤 자릿수를 비교해가며 각 알파벳에 숫자를 높은 순서부터 할당하는 방식이었다. 하지만 하다보니 구현이 너무 복잡해지고 큰 문제점이 있었다. 

 

만약 ABC + BEG 이런 경우  A보다 B에 높은 숫자가 할당되어야 하지만 문자열의 길이가 같다보니 정렬이 A가 더 먼저 할당되게 된다. 따라서 접근 방식을 바꿔야했고 다른 풀이의 접근 방식을 한 번 본 후 다시 풀어보았다.

 

이 방식은 다음과 같은 규칙을 이용한다.

ABC = 100*A + 10*B + C

 

즉, 알파벳 각각이 계산될 값을 통해 우선순위를 정할 수 있다.

따라서 알파벳이 여러번 나올때도 쉽게 처리할 수 있다.

 

 for(string x: v){
        for(int i = 0; i < x.length(); i++){
            int digit = x.length() - i;
            int value = 1;
            for(int j = 0; j < digit - 1; j++){
                value *= 10; 
            }
            alpha[x[i] - 'A'] += value;
        }
    }

위의 for문을 통해 각 알파벳이 가지는 자리수의 값을 계산해주고 alpha 배열의 알맞은 위치에 값을 더해준다.

 

sort(alpha, alpha + 26, desc);

    int num = 9;
    int sum = 0;
    int i = 0;
    while(alpha[i] != 0){
        sum += alpha[i] * num;
        num --;
        i++;
    }
    cout << sum;

그리고 alpha 배열을 내림차순 정렬해주면 높은 값을 가지는 알파벳부터 높은 숫자를 곱해줄 수 있다.

 

느낀점

알파벳마다 가중치를  두는 발상을 하는 것이 기발했고 자주 써먹을 것 같다.

그리디 문제라는데 가중치 큰 순서대로 높은 숫자 곱해주는 거라 그리디인건가? 약간 애매하다..

 

보충

문자열 최대 길이가  8밖에 안되고 개수도 최대 10개라 브루트포스와 백트래킹으로도 풀 수 있다고 한다.

---