알고스팟 - KOOGLE

[문제 링크]

문제 자체는 입력을 문자열로 받아 문자의 아스키코드로 문자,숫자만 체크하면 되는 간단한 문제다.

다만 이 문제에서 주의해야할 점은 입력받는 문자열의 길이가 최대 1000개라는 점이다

문제를 제대로 읽지 않고 그냥 제곱연산을 했다가 오답이 떴는데 Strength(x) = 26^A * 10^B이므로 숫자로만 1000개 채워졌다고 해도, 10^1000이다.

크게 봐줘서 64비트 정수형을 쓴다고 해도 2^64-1은 아득히 넘어버린다.(Big Integer 라이브러리를 써도 안될거같다.)

그래서 이 문제는 그냥 pow로 구하기엔 자료형 범위를 초과하는 값은 정확한 비교가 되질 않는다.

하지만 이 문제는 암호의 강도가 정확히 몇인지를 알아야 하는 문제가 아니고, 뭐가 더 강한지만 고려하면 되기 때문에 그냥 log를 씌워서 계산한 후 비교하면 된다.

#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
int testcase,n;
string str;
long double Strength(const string& str){
    int num=0,chr=0;
    for(int i = 0; i<str.length(); i++){
        if(str[i]>=97 && str[i]<=122) chr++;
        else num++; 
    }
    return chr*log(26) + num*log(10);
}
int main(){
    cin>>testcase;
    while(testcase--){
        string maxStr;
        long double maxValue = 0;
        cin>>n;
        for(int i = 0; i<n; i++){
            cin>>str;
            long double cur = Strength(str);
            if(cur > maxValue){
                maxStr = str;
                maxValue = cur;
            }
            else if(cur == maxValue && maxStr.compare(str)>0) maxStr = str;
        }
        cout << maxStr << endl;
    }
}

위도 accept는 되지만 밑은 메모리와 시간을 좀 더 줄인 코드이다. 

#include <cstdio>
#include <cmath>
#include <cstring>
int testcase,n;
char str[1001];
long double Strength(char* str){
    int num=0,chr=0;
    for(int i = 0; i<strlen(str); i++){
        if(str[i]>=97 && str[i]<=122) chr++;
        else num++; 
    }
    return chr*log(26) + num*log(10);
}
int main(){
    scanf("%d",&testcase);
    while(testcase--){
        char maxStr[1001];
        long double maxValue = 0;
        scanf("%d",&n);getchar();
        for(int i = 0; i<n; i++){
            scanf("%s",str);
            long double cur = Strength(str);
            if(cur > maxValue){
                strcpy(maxStr,str);
                maxValue = cur;
            }else if(cur == maxValue &&strcmp(maxStr,str)>0)strcpy(maxStr,str);
        }
        printf("%s\n",maxStr);
    }
}