JavaScript에서 문자열의 일부를 재배열해 다른 문자열을 만들 수 있을까?

문제 정의

두 개의 문자열 str1과 str2를 인자로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 str1에 포함된 문자들 중 일부 또는 전부를 재배열하여 str2와 동일한 문자열을 만들 수 있으면 true를, 그렇지 않으면 false를 반환해야 합니다.

예를 들어 str1 = 'rkqodlw', str2 = 'world'라고 가정해 보겠습니다. str1에는 'w', 'o', 'r', 'l', 'd'가 모두 포함되어 있으므로, 이 문자들을 재배열하면 'world'를 만들 수 있습니다. 따라서 함수는 true를 반환해야 합니다.

풀이 코드

const str1 = 'rkqodlw';
const str2 = 'world';

const canForm = (str1 = '', str2 = '') => {
  if(str1.length < str2.length){
    return false;
  }
  const res = str2.split('');
  str1.split('').forEach(val => {
    if(res.includes(val)){
      res.splice(res.indexOf(val), 1);
    }
  });
  return res.length === 0;
};

console.log(canForm(str1, str2));

코드 설명

이 풀이의 핵심 로직은 다음과 같습니다.

1. 길이 사전 검사: str1의 길이가 str2보다 짧다면 어떻게 재배열하더라도 str2를 만들 수 없으므로 즉시 false를 반환합니다. 불필요한 연산을 줄여 효율성을 높이는 단계입니다.

2. 대상 문자열 배열화: str2를 split('')으로 문자 배열로 변환합니다. 이 배열은 아직 채워야 할 문자들의 목록 역할을 합니다.

3. 문자 매칭 및 제거: str1의 각 문자를 순회하면서, 해당 문자가 res 배열에 존재하면 splice()로 제거합니다. 이렇게 하면 중복된 문자가 정확히 개수만큼만 소모됩니다.

4. 최종 판정: 모든 순회가 끝난 후 res 배열이 비어 있다면(length === 0) str1의 문자들로 str2를 완전히 구성할 수 있다는 의미이므로 true를 반환합니다.

출력 결과

true

마무리

이 알고리즘은 시간 복잡도가 O(n × m)으로, 문자열 길이가 크지 않은 경우 충분히 실용적입니다. 더 나은 성능이 필요하다면 각 문자의 빈도수를 객체나 Map으로 미리 계산한 뒤 비교하는 O(n + m) 방식으로 개선할 수도 있습니다.