JavaScript로 문자열을 결합해 회문 쌍 찾기

문제 정의

문자열 배열을 유일한 인자로 받아, 두 문자열을 서로 결합했을 때 새로운 회문(palindrome) 문자열이 되는 모든 인덱스 쌍을 배열 형태로 반환하는 JavaScript 함수를 작성해야 합니다.

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

const arr = ['tab', 'cat', 'bat'];

이 경우 기대되는 출력은 다음과 같습니다.

const output = [[0, 2], [2, 0]];

출력 설명

'battab'과 'tabbat' 두 문자열 모두 앞에서 읽으나 뒤에서 읽으나 동일한 회문이기 때문입니다.

구현 예제

이 문제를 해결하는 전체 코드는 다음과 같습니다.

const arr = ['tab', 'cat', 'bat'];

// 문자열이 회문인지 검사하는 보조 함수
const isPalindrome = (str = '') => {
   let i = 0;
   let j = str.length - 1;
   while (i < j) {
      if (str[i] != str[j]) return false;
      i++;
      j--;
   };
   return true;
};

// 회문이 되는 모든 인덱스 쌍을 찾는 메인 함수
const palindromePairs = (arr = []) => {
   const res = [];
   for (let i = 0; i < arr.length; i++) {
      for (let j = i + 1; j < arr.length; j++) {
         if (isPalindrome(arr[i] + arr[j])) {
            res.push([i, j]);
         }
         if (isPalindrome(arr[j] + arr[i])) {
            res.push([j, i]);
         }
      }
   }
   return res;
};

console.log(palindromePairs(arr));

코드 설명

먼저 보조 함수 isPalindrome()은 투 포인터(two pointer) 기법을 활용해 문자열이 회문인지 판별합니다. 문자열의 양쪽 끝에서 시작한 두 포인터가 중앙으로 이동하면서 각 위치의 문자가 일치하는지 검사하다가, 하나라도 일치하지 않으면 즉시 false를 반환합니다.

메인 함수 palindromePairs()는 배열 내 모든 가능한 조합을 생성하고, 결합 결과가 회문 조건을 만족하는 쌍의 인덱스를 res 배열에 추가합니다. 여기서 중요한 점은 각 쌍에 대해 [i, j]와 [j, i] 두 가지 순서를 모두 검사한다는 것입니다. 문자열을 붙이는 순서에 따라 회문 여부가 달라질 수 있기 때문입니다. 또한 내부 루프가 j = i + 1부터 시작하므로 같은 쌍을 중복해서 검사하지 않으면서도 모든 조합을 빠짐없이 확인할 수 있습니다.

시간 복잡도

이 풀이의 시간 복잡도는 O(n² × k)입니다. 여기서 n은 배열의 길이, k는 문자열의 평균 길이입니다. 모든 쌍의 조합(O(n²))을 검사하고, 각 조합마다 회문 여부 확인(O(k))이 필요하기 때문입니다. 소규모 입력에는 충분히 효율적이지만, 입력 크기가 매우 클 경우 해시 맵을 활용한 최적화 풀이를 고려할 수 있습니다.

출력 결과

콘솔에 출력되는 최종 결과는 다음과 같습니다.

[ [ 0, 2 ], [ 2, 0 ] ]