Highest Value Palindrome

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

✅ Problem Summary

주어진 문자열 내의 숫자를 수정하여 팰린드롬(palindrome)을 만든다고 할 때, 숫자를 최대 k개 만큼 수정하여 가장 큰 값을 가지는 팰린드롬을 만드는 문제

---

📑 My Answer

• 모든 테스트 케이스 통과

 def highestValuePalindrome(s, n, k):
    s_lis = list(map(int, s))
    changed = [0] * (round(n/2) + 1)

    i = 0
    while k > 0 and i < round(n/2):
        if s_lis[i] != s_lis[-i - 1]:
            max_val = max(s_lis[i], s_lis[-i - 1])
            s_lis[i] = s_lis[-i - 1] = max_val
            changed[i] = 1
            k -= 1
        i += 1

    i = 0
    while k > 0 and i < round(n/2)+1:
        if s_lis[i] != 9:
            if n%2!=0 and True not in changed and k == 1:
                s_lis[round(n/2)] = 9
            elif n%2==0 and True not in changed and k == 1:
                break
            else:
                s_lis[i] = s_lis[-i - 1] = 9
                k -= (2 - changed[i])
        i += 1

    res = ''.join(map(str, s_lis))
    print(res)
    return '-1' if res != res[::-1] else res

📌 코드 구현 설명

• 문자열 처리를 1차, 2차로 나누어 수행
• 우선 1차 처리에서 문자열 양 극단에서부터 중앙으로 숫자 짝(pair)을 만들어 비교하고, 그 중 작은 값을 큰 값으로 치환하여 팰린드롬을 만듦
• 1차 처리에서 팰린드롬을 만들어야 한다는 조건은 달성하였기 때문에, 2차 처리에서는 최댓값을 만드는 작업을 수행함 → 팰린드롬을 유지하면서 자릿수 들을 최대한 많이 9로 치환
• 1차, 2차 처리 모두 숫자를 변경할 때 마다 k값을 감소시켜주고, k값이 0이 되면 종료되도록 함
• 1차에서는 숫자 짝에서 둘 중 하나의 값만 변경되기 때문에 k가 항상 1씩 감소하지만, 2차에서는1차에서 한번 바뀌었던 숫자 짝은 1 씩 감소, 바뀌지 않았던 숫자 짝은 2 씩 감소 하도록 설계 → 9로 치환할 때 숫자 짝, 즉 두 개의 숫자를 다 바꿔주어야 하므로 기본적으로는 2 씩 감소하지만 중복으로 감소시키지 않도록 1차에서 바뀐 숫자 짝을 만났을 때는 1 씩 감소하는 형태
• (예외 처리) 문자열의 길이가 홀수이고 모든 자릿수가 바뀐적이 없으며 k=1 인 경우에는 중앙의 숫자를 9로 치환, 같은 조건에 문자열 길이가 짝수인 경우에는 바꿀 수 있는 숫자가 없으므로 종료

---

💼 Takeaway

• 어떤 정해진 알고리즘을 적용하여 푸는 문제가 아니라, 스스로 규칙을 만들고 조건들을 설정해서 푼 문제가 처음이라 풀면서도 이게 맞는지 의문이 들었다.

• 노트에 끄적이며 코드가 돌아가야 하는 구조를 시각화 한 것이 도움이 많이 되었다. 앞으로도 차근히 노트에 적고, 그려가며 문제를 풀어보려 한다.

---