Highest Value Palindrome

사이트: HackerRank
난이도: 미디움
분류: String

문제

정수형 문자열과 최대 변경 횟수가 주어졌을 때, 각 자리수를 변경하여 회문으로 만들어라. 회문으로 변경하는 경우의 수가 2가지 이상일 경우 가장 큰 값을 반환하라.

회문이란 거꾸로 뒤집어도 동일한 형태로 읽을 수 있는 문자열을 뜻한다.
ex) 스위스, 기러기 등...

다음과 같이 주어지면 992299를 반환해야 한다.

// 문자열의 길이
n = 6 
// 변경가능 최대 횟수
k = 3
// 정수형 문자열
092282

1. 나의 풀이

문자열 문제는 생각보다 규칙 찾는데서 오래 걸리는 것 같다. 비슷한 유형의 문제를 풀어보면서 풀이 속도를 늘려야 할 것 같다...

function highestValuePalindrome(s, n, k) {
    // Write your code here
    const half = Math.floor(n / 2);
    const arr = Array.from(s);
    const alters = [];
    
    for (let i = 0; i < half; i++) {
      	// 앞과 뒤를 비교하면서 다른 경우 인덱스를 기록한다.
        if (arr[(arr.length - 1) - i] !== arr[i]) {
            alters.push(i);
          
          	// 이 때 이미 변경될 수보다 변경 가능수가 작을 경우 -1을 반환한다.
            if (alters.length > k) {
                return '-1';
            }
        }
    }

  	// 대체 가능한 수를 제외한 나머지 변경가능 수를 가져온다.
    let lk = k - alters.length;
    for (let i = 0; i < half; i++) {
        const backIdx = (arr.length - 1) - i;
        
        if (alters.includes(i)) {
          	// 변경해야 하는 요소일 경우 앞, 뒤를 비교하여 큰 값을 가져온다.
            const alter = arr[i] > arr[backIdx] 
                ? arr[i]
                : arr[backIdx];

          	// 변경해야 하는 요소일 경우라도 나머지가 남아 있으면 앞, 뒤 모두 9로 변경하는 것이 가능하다.
          	// 인덱스가 0부터 시작하기 때문에 자연스럽게 큰 숫자로 변환이 가능하다.
            if (lk > 0 && alter != 9) {
                arr[i] = 9;
                arr[backIdx] = 9;
              	// 이미 변경 해야 하는 요소의 카운트를 뺐기 때문에 1만 감소시킨다.
                lk -= 1;

            } else {
              	// 나머지 값이 없을 경우 큰 값으로 대체한다.
                arr[i] = alter;
                arr[backIdx] = alter;
            }

        } else {
          	// 나머지가 남아있고 현재 값이 9가 아니면 앞, 뒤 모두 9로 변경한다.
          	// 현재 값이 9인지 검사하는 것이 중요하다.
            if (lk > 1 && arr[i] != 9) {
                arr[i] = 9;
                arr[backIdx] = 9;
                lk -= 2;
            }
        }
    }
    
  	// 모두 변경하고 나서도 나머지가 남아있는 상황이면 center를 변경한다.
    if (lk > 0 && n % 2 === 1) {
        arr[half] = 9;
    }
    
    return arr.join('');
}

2. 다른사람의 풀이

바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.