자바스크립트로 두 문자열의 차이점 찾는 방법

문제 소개

두 개의 문자열 s와 t가 주어집니다. 문자열 t는 문자열 s를 무작위로 섞은 뒤, 임의의 위치에 글자 하나를 추가하여 생성된 것입니다.

이제 두 문자열을 인수로 받아 t에 추가된 바로 그 글자를 반환하는 자바스크립트 함수를 작성해야 합니다.

예를 들어 입력 문자열이 다음과 같다면,

const s = "abcd", t = "abcde";

출력 결과는 다음과 같아야 합니다.

const output = "e";

'e'가 s에는 없고 t에만 존재하는, 즉 추가된 글자이기 때문입니다.

해결 접근 방식: XOR 연산 활용

이 문제는 XOR(배타적 논리합) 연산의 성질을 이용하면 우아하게 해결할 수 있습니다. XOR은 같은 값끼리 연산하면 0으로 상쇄되고, 한 번만 등장한 값은 그대로 남는다는 특징이 있습니다.

따라서 s와 t에 속한 모든 글자의 문자 코드를 차례로 XOR하면, 두 문자열에 공통으로 존재하는 글자들은 서로 상쇄되어 사라지고 마지막에는 추가된 글자의 정보만 남게 됩니다.

구현 예제

const s = "abcd", t = "abcde";
const findTheDifference = (s, t) => {
    let a = 0, b = 0; let charCode, i = 0;
    while(s[i]){
        a ^= s.charCodeAt(i).toString(2);
        b ^= t.charCodeAt(i).toString(2);
        i++;
    };
    b^=t.charCodeAt(i).toString(2);
    charCode = parseInt(a^b,2);
    return String.fromCharCode(charCode);
};
console.log(findTheDifference(s, t));

출력 결과

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

e

더 간단한 대안: 문자 코드의 합 비교하기

XOR 대신 각 문자열의 문자 코드 합을 구한 뒤 그 차이를 활용하는 방법도 있습니다. t의 문자 코드 합에서 s의 문자 코드 합을 빼면, 그 차이값이 곧 추가된 글자의 문자 코드가 됩니다.

const findTheDifference = (s, t) => {
    let sumS = 0, sumT = 0;
    for (let i = 0; i < s.length; i++) {
        sumS += s.charCodeAt(i);
        sumT += t.charCodeAt(i);
    }
    return String.fromCharCode(sumT - sumS);
};
console.log(findTheDifference("abcd", "abcde")); // "e"

두 방법 모두 시간 복잡도가 O(n)으로 효율적이며, 코드의 가독성과 상황에 따라 적절한 방식을 선택해 사용하면 됩니다.