[HackerRank] 펠린드롬 최대값 만들기

얼마 전에 어느 회사의 서류 전형을 통과해서 코딩 테스트에 참석할 예정인데, 이 과정에서 HackerRank 라는 코딩 문제풀이 사이트를 알게 됐다.

사이트에는 튜토리얼이 30일 코스, 10일 코스 등으로 잘 준비되어 있는데, 차근차근 풀어보다가 랜덤으로 문제를 선택하는 버튼을 눌렀더니 이 문제와 마주하게 됐다.

펠린드롬은 전에도 구현한 적이 있었지만,
주어진 횟수만을 사용하여 최대값을 만드는 건 처음이라 꽤 어려웠다.

처음에는 순수하게 혼자의 힘으로 시도했었는데, 간단한 케이스는 통과했지만 아예 불가능한 경우와 이미 펠린드롬인 숫자를 최대값으로 만드는 등의 케이스는 많이 통과하지 못했다.
그래서 해당 페이지에 있는 C++ 예시 코드를 참고해서 힌트를 얻었다.

문제와 내가 작성한 답안은 아래와 같다.

• 주어지는 매개변수는 3가지로 아래와 같다.
  s: 숫자로 구성된 문자열
  n: s의 길이
  k: 주어진 숫자를 변경할 수 있는 횟수
• s를 k번 내에 펠린드롬이면서 가장 큰 숫자로 만들어 리턴해야 하며, 주어진 조건에서 최대 펠린드롬을 만드는 것이 불가능할 경우 -1을 리턴한다.
  (s='1231', k=3 인 경우, '9339'를 만들어야 한다. 숫자 하나를 바꿀 때마다 k는 1씩 줄어든다.)

function highestValuePalindrome(s: string, n: number, k: number): string {
	const arr = s.split('');
	// answer는 답을 담을 빈 배열
	let answer = new Array(n);
    // check는 양쪽 숫자 중 한쪽만 바꿨을 경우를 표시하는 배열(나중에 최대값을 만들 때 이용한다.)
  	let check = new Array(n).fill(0);
  
  	// 포인터 2개 만들기
    let l = 0;
    let r = n - 1;
  
	// 펠린드롬을 만들기 위해 바꿔야 할 횟수 계산하기
    let count = 0;
    while(l <= r) {
      if(arr[l] !== arr[r]) {
        count++
        l++;
        r--;
      } else {
        l++;
        r--;
      }
    }
    
    // 주어진 k보다 바꿔야 할 횟수가 많다면 불가능하므로 -1 리턴
    if(count > k) return '-1';

	// 포인터 초기화 및 펠린드롬 만들기
    l = 0;
    r = n - 1;
    while(l <= r) {
      if(l == r) {
        answer[l] = arr[l];
        break;
      }
      if(arr[l] == arr[r]) {
        answer[l] = arr[l];
        answer[r] = answer[l];
      } else {
        if(arr[l] > arr[r]) {
          answer[l] = arr[l];
          answer[r] = arr[l];
          // 오른쪽 숫자가 작으면, 오른쪽 숫자를 왼쪽 숫자와 일치시키고,
          // k를 1 줄이고, check 배열의 해당 오른쪽 위치에 1을 추가
          k--;
          check[r] = 1;
        } else {
          answer[l] = arr[r];
          answer[r] = arr[r];
          k--;
          check[l] = 1;
        }
      }
      l++;
      r--;
    }

	// 펠린드롬 만든 후 k가 음수이면 조건을 위반했으므로 -1 리턴
    if(k < 0) return '-1';

	// 포인터 초기화 및 최대값 만들기
    l = 0;
    r = n - 1;
    while(l <= r) {
      if(l == r) {
        if(answer[l] < 9 && k >= 1) {
          answer[l] = 9;
          k--;
          break;
        }
      }
      if(answer[l] < 9) {
        if(check[l] == 0 && check[r] == 0 && k >= 2) {
          // check 값이 0이란 것은 위에서 해당 숫자를 변경하지 않았다는 것이므로 둘다 9로 바꾸고 k는 2를 줄인다.
          answer[l] = 9;
          answer[r] = 9;
          k -= 2;
        } else if((check[l] == 1 || check[r] == 1) && k >= 1 ) {
          // check 값이 1이란 것은 위에서 해당 숫자 한 쪽만 변경했다는 것이므로 둘다 9로 바꾸되,
          // 위에서 바꾼 수는 애초에 9로 바꾼다고 가정하고
          // 건들지 않은 숫자만 9로 바꾸고 k는 1만 줄인다.
          answer[l] = 9;
          answer[r] = 9;
          k--;
        }
      }
      l++;
      r--;
    }
    
    // 문자열로 리턴해야 하므로
    return answer.join('');
}

조건에 맞춰서 해결해야 할 문제들을 하나씩 정리해서 단계별로 풀어야 하는 것이 쉽지는 않았다.
계속해서 쪼개서 생각하고 답을 고민하는 습관을 길러야 한다고 느꼈고, 문제풀이는 역시 끊임없이 해야 된다는 것 또한 다시 느꼈다.

그리고 다른 사람들의 풀이를 아예 안 본 건 아니었는데, 주석이 있어도 그 코드를 이해하는게 더 어렵고 시간도 오래 걸려서 도움이 됐다기 보다는 남의 코드를 보는 것 또한 공부가 될 거라는 생각 그리고 남이 잘 읽을 수 있게 쓰는 것도 능력이 아닐까 라는 생각도 하게 됐다.

코딩 문제풀이는 여러모로 도움이 많이 되는 것 같다.
해결했을 때의 뿌듯함을 기억하고, 계속 계속 해봐야겠다!