[C++][백준 BOJ]1339_단어 수학

문제 번호

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

1339번: 단어 수학

 

 

알고리즘 분류

그리디(greedy).

 

문제 풀이

 각 알파벳에 어떤 숫자를 대응할지 고민했다. 대충봐도 가장 높은 자리수를 갖는 알파벳에 가장 큰 수를 넣으면 될것 같지만, 같은 자리수를 여러번 같은 알파벳들이 등장하거나 더 낮은 자리수에 등장하더라도 더 많이 등장해서 더 큰 수를 배정받아야 하는 경우등이 있었다. 

 그래서 각 알파벳들마다 점수를 매기기로 했다.(점수를 매기기위한 벡터와 그 벡터의 초기화).

vector<pair<char,int>> alpha(26);
    char tmp = 'A';
    // init
    for(int i=0; i<26; i++)
    {
        alpha[i] = {tmp,0};
        tmp++;
    }

점수를 매기는 방식은 1의 자리에 등장하면 10^0 점, 10의 자리에 등장하면 10^1점을 부여하는 방식으로 각 자리수 마다 10배의 배점을 부여하였다.

// 각 알파벳 마다 점수를 배정한다.
    for(int i=0; i<word.size(); i++)
    {
        string temp=word[i];
        for(int j=temp.length()-1; j>=0; j--)
        {
            alpha[ temp[j] - 'A'].second += pow(10,temp.length()-1-j);
        }
    }

 매긴 점수를 기준으로 내림차순 정렬을 한뒤, 각 알파벳에 높은 점수부터 숫자를 지정하였다. 가장 높은 점수를 갖는 알파벳은 9, 그 다음 점수를 갖는 알파벳은 8, 이런식으로 0 까지 알파벳마다 숫자를 지정하였다.

 // 점수기준 내림차순으로 정렬한다.
    sort(alpha.begin(), alpha.end(), compare);

    // 점수를 기준으로 알파벳마다 숫자를 할당한다.
    for(int i=0; i<10; i++)
        alpha[i].second = 9-i;

 마지막으로 배정한 숫자를 바탕으로 정답을 계산하면 된다.

for(int i=0; i<word.size(); i++)
    {
        string temp=word[i];
        for(int j=temp.length()-1; j>=0; j--)
        {
            for(int k=0; k<10; k++)
            {
                if(temp[j] == alpha[k].first)
                {
                    answer += alpha[k].second * pow(10,temp.length()-1-j);
                    break;
                }
            }
        }
    }

전체코드

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

bool compare(pair<char,int> a, pair<char,int> b)
{
    return a.second > b.second;
}

int Solution(vector<string> word)
{
    int answer = 0;    
    
    vector<pair<char,int>> alpha(26);
    char tmp = 'A';
    // init
    for(int i=0; i<26; i++)
    {
        alpha[i] = {tmp,0};
        tmp++;
    }

    // 각 알파벳 마다 점수를 배정한다.
    for(int i=0; i<word.size(); i++)
    {
        string temp=word[i];
        for(int j=temp.length()-1; j>=0; j--)
        {
            alpha[ temp[j] - 'A'].second += pow(10,temp.length()-1-j);
        }
    }

    // 점수기준 내림차순으로 정렬한다.
    sort(alpha.begin(), alpha.end(), compare);

    // 점수를 기준으로 알파벳마다 숫자를 할당한다.
    for(int i=0; i<10; i++)
        alpha[i].second = 9-i;

    for(int i=0; i<word.size(); i++)
    {
        string temp=word[i];
        for(int j=temp.length()-1; j>=0; j--)
        {
            for(int k=0; k<10; k++)
            {
                if(temp[j] == alpha[k].first)
                {
                    answer += alpha[k].second * pow(10,temp.length()-1-j);
                    break;
                }
            }
        }
    }

    return answer;
}

int main()
{
    int N; cin >> N;
    vector<string> word;
    for(int i=0; i<N; i++)
    {
        string input; cin >> input;
        word.push_back(input);
    }

    cout << Solution(word);

    return 0;
}

 

특이사항

 VS Code에서 문제풀이를 진행하는데 code run을 할때 예상값과 결과값이 1,2 정도 차이가 나는것을 발견하였다. 그런데 모든 테스트케이스에서 그런것이 아니라 일부 테스트케이스에서만 이런 현상이 발생하였다. 그래서 디버깅을 해보았는데 디버그로 답을 도출할때는 정확한 값이 나온다.........

 pow함수를 사용할때 큰값이 사용되면 오차가 발생한다고하는데 그런 이유때문에 디버깅없이 실행하였을때 오차가 발생한것 같다. 

 가능하면 pow함수는 사용을 자제하도록해보자.