백준 17609번

QUESTION LINK

주어지는 문자열에 대해 해당 문자가 바로 좌우 대칭인지, 한 문자를 빼야 좌우 대칭인지를 파악하는 문제였습니다. 문제를 읽자마자 해결을 하기 위한 가장 큰 개념이 ‘투 포인터’라는 것은 파악할 수 있었습니다. 하지만, 해당 문제에서 주어진 것과 같이, 문자 하나를 뺐을 때 좌우 대칭인지에 대해서도 알아내야 하는 부분이 있었는데, 이 부분에서 조건문을 복잡하게 걸고 시작해 문제가 되었습니다.

결론적으로는, 좌우 대칭의 여부를 확인하는 함수를 만들고, 해당 함수를 통과하지 못하는 경우에 대해 해당 부분에 대한 좌 ∙ 우로 뺀 문자열을 한 번 더 검사하여 문제를 해결할 수 있었습니다.

위와 같은 순서로 문제를 해결하고자 하였으며, 이를 위해 먼저 좌우 대칭을 확인하는 코드를 작성했습니다.

const getIsPalindrome = (string) => {
  let left = 0;
  let right = string.length - 1;
  let isPalindrome = true;

  while (left < right && isPalindrome) {
    if (string[left] === string[right]) {
      // 좌우가 일치할 시 양쪽 다 한 칸씩 당겨서 다시 검사
      left += 1;
      right -= 1;
    } else {
      isPalindrome = false;
      // 좌우 대칭이 아닐 시 잘못되었음을 표시
    }
  }

  return { isPalindrome, left, right };
  // 잘못된 지점의 위치가 필요하므로, left, right를 함께 출력
};

위와 같은 함수를 만들고, 이 함수와 더불어 위에서 설명되었던 그림의 형태로 문제를 해결하고자 하였습니다.

// stringArray는 문제에서 주어진 문자열들의 배열
const resultArray = stringArray.map((string) => {
  const { isPalindrome, left, right } = getIsPalindrome(string);
  if (isPalindrome) return 0;
  // 처음에 좌우 대칭일 시, 바로 0을 리턴

  const { isPalindrome: isPalindromeFromLeft } = getIsPalindrome(
    string.substring(left + 1, right + 1)
  );
  if (isPalindromeFromLeft) return 1;
  // 왼쪽을 당긴 값이 좌우 대칭일 시 1을 리턴
  const { isPalindrome: isPalindromeFromRight } = getIsPalindrome(
    string.substring(left, right)
  );
  if (isPalindromeFromRight) return 1;
  // 오른쪽을 당긴 값이 좌우 대칭일 시 1을 리턴
  return 2;
});

이러한 흐름을 통해서 문제를 해결할 수 있었습니다. 이 문제는 사실 자체적인 어려움이 크게 없는 문제였습니다. 하지만, 처음에 좌우 대칭을 검사하고, 좌우 대칭이 아닌 경우 한 번 더 각 상황에 맞는 검사를 하는, isPallindromeLeft, isPallindromeRight 값을 구하는 작업을 해야하는 상황에 대해서 while문을 통한 조건식으로만 해결하려고 하여, 계속 문제가 틀리거나 시간 초과라는 결과가 나왔습니다. 이와 같이, 문자열 내에서도 추가적인 같은 검사가 필요한 부분에 대해서 미리 함수를 만들어 처리하는 방법을 먼저 생각해 볼 필요가 있음을 이번 문제를 통해 깨달았습니다.

GITHUB  EMAIL