백준 1339 단어수학 쉬운 풀이 (C++/CPP)

문제 추상화

• 알파벳에 숫자를 대입해서 최대의 수를 찾는문제
• 앞자리일수록 큰게 좋음 >> 그리디 - 숫자

아이디어

• 모든 숫자를 알파벳에 대입해서 최대값을 찾는 경우
  • 시간복잡도가 관건
  • 시간복잡도 : 알파뱃 최대 갯수 ^ 알파벳 최대갯수 > 10^10 > 시간초과
• 앞자리일수록 큰 숫자로
  • 만약 두개의 단어가 길이가 같은데 첫자리가 다른경우?
  • 뒤에 더 앞자리가 들어오는 알파벳에 큰 숫자를 넣어야함
  • 각 알파벳이 들어간 위치를 계산하여 점수를 매기는 수밖에없음
• 단어의 길이를 먼저 구함
• 단어의 위치에서 알파벳의 평가점수를 넣어줌
• 평가점수가 높은 순으로 높은 숫자를 넣음
• 단어의 합을 구함

시간복잡도 계산

• 모든 단어에 대해서 : O(N)
• 단어의 길이를 먼저 구함 : O(1)
• 단어의 위치에서 알파벳의 평가점수를 넣어줌 : O(10)
• 평가점수가 높은 순으로 높은 숫자를 넣음
• 단어의 합을 구함 : O(N)
• 시간복잡도 : O(N*10 + N) : O(10N) = 100

인트 계산

• 단어의 합 최대값 : 10 * 9999999999 = 1e11 >> long long 사용
• 알파벳의 평가점수 : 평가점수 최대값 : 10 * 1e10 >> long long 사용

코드

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int alpha[26];
 
int main() {
    int N; cin >> N;
    
    fill(alpha, alpha+26, 0);
    
    for(int i=0; i<N; i++) {
        string s; cin >> s;
        for(int i=0; i<s.size(); i++) {
            // 알파벳 숫자로 변환
            int ec = s[i] - 'A';
            // 알파벳 평가점수
            alpha[ec] += pow(10,s.size()-1-i);
        }
    }
    
    sort(alpha, alpha+26, greater<int>());
    
    int rs=0;
    int tmp = 10;
    
    for(int i=0; i<10; i++) {
        tmp--;
        rs += alpha[i] * tmp;
    }
    
    cout << rs << '\n';
    
    return 0;
}
 

문제유형

• 그리디 - 숫자관련 최소 최대
  • 최대 : 앞자리일수록 큰 수 사용, 최소는 그 반대
  • 엣지값 -1,0,1 조심

비슷한 문제

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