해커랭크 Higest Value Palindrome (C++)

안녕하세요~

오늘은 해커랭크 "Higest Value Palindrome" 문제를 풀어봐요!

 

 

https://www.hackerrank.com/challenges/richie-rich/problem?isFullScreen=true

Highest Value Palindrome | HackerRank

 

가장 큰 팰린드롬을 찾는 문제인데

팰린드롬이란 좌우 대칭인 배열이에요!

 

사실 이문제는 모든 테케를 통과하진 못했지만....

일단 한데까지 올립니다 ㅜㅜ

 

테케 10, 16, 17, 24, 25, 28, 29를 통과 못하네요....ㅜㅜ

아시는분 알려주시면 매우매우 감사하겠습니다!!

 

bool IsPal(string s)
{
    bool isPalin = true;
    for (long long i = 0; i < s.length(); i++)
    {
        long long idx = s.length() - 1 - i;
        if (s[i] != s[idx])
        {
            isPalin = false;
            break;
        }
    }

    return isPalin;
}

string highestValuePalindrome(string s, int n, int k) {
    if (n == 1)
    {
        if (k > 0)
        {
            return "9";
        }
        else {
            return s;
        }
    }

    if (n % 2 == 0)
    {
        n /= 2;
    }
    else
    {
        n = n / 2;
    }

    string sc = s;
    for (long long i = n - 1; i >= 0; i--)
    {
        long long idx = sc.length() - 1 - i;
        if (sc[i] != sc[idx])
        {
            if (k == 0)
            {
                break;
            }
            long long change = s[i] > s[idx] ? s[i] : s[idx];
            sc[i] = change;
            sc[idx] = change;
            k--;
        }
    }

    if (k == 0 && !IsPal(sc))
    {
        return "-1";
    }

    for (long long i = 0; i < n; i++)
    {
        long long idx = s.length() - 1 - i;

        if (sc[i] != '9')
        {
            if (k >= 2)
            {
                sc[i] = '9';
                sc[idx] = '9';
                k -= 2;
            }
            else
            {
                if ((sc[i] != s[i] && sc[idx] == s[idx] ) || (sc[i] == s[i] && sc[idx] != s[idx]))
                {
                    sc[i] = '9';
                    sc[idx] = '9';
                    k--;
                }
            }
        }
    }

    if (k > 0 && s.length() % 2 == 1)
    {
        sc[s.length() / 2] = '9';
    }

    return sc;
}