[21740] 도도의 수학놀이

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

21740번: 도도의 수학놀이

<문제>

정렬의 기준은 "[16496] 큰 수 만들기"와 마찬가지로 string의 '+'와 부등호를 통한 사전순 비교로 간단히 구현된다.

해당 문제와 달리, 180도 회전하는 부분에 대한 처리와 하나의 수를 추가 할 수 있다는 조건이 추가되었고,

회전에 대한 처리는 간단히 정렬 전과 후에 한번씩 돌려줄 수 있다.

추가할 수는 가장 길이(자리수)가 길면서, 가장 큰 수이다. 이를 추가해 준 뒤에 사전순으로 정렬하면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n;
string pb;
vector<string> v;
string rev(string s) {
    int i, S = s.length();
    string ret = "";
    for (i = 0; i < S; i++) {
        if (s[i] == '6')
            ret += '9';
        else if (s[i] == '9')
            ret += '6';
        else
            ret += s[i];
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
bool cmp(string A, string B) {
    if (A.length() == B.length()) return stoi(A) < stoi(B);
    return A.length() < B.length();
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int i;
    for (i = 0; i < n; i++) {
        string in;
        cin >> in;
        v.push_back(rev(in));
    }
    pb = v[0];
    for (i = 1; i < n; i++)
        if (cmp(pb, v[i]) == true) pb = v[i];
    v.push_back(pb);
    sort(v.begin(), v.end(),
         [](string A, string B) -> bool { return (A + B) > (B + A); });
    string ans = "";
    int S = n + 1;
    for (i = S - 1; i >= 0; i--) ans += rev(v[i]);
    cout << ans;
    return 0;
}

비슷한 문제들이 꽤 많다. 

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

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