389. Find the Difference

2026-03-22

리트코드 389번 풀이

문제

Find the Difference

풀이 1

아이디어

문자열 s와 t를 정렬한 뒤에 각각의 요소를 비교해서 다른 요소를 반환하는 방식으로 풀었다. 만약 모든 요소가 같다면, t의 마지막 요소가 s에는 없는 요소이므로 t의 마지막 요소를 반환한다.

코드

function findTheDifference(s: string, t: string): string {
  const sArr = s.split('').sort();
  const tArr = t.split('').sort();

  for (let idx = 0; idx < sArr.length; idx++) {
    if (sArr[idx] !== tArr[idx]) return tArr[idx];
  }

  return tArr[tArr.length - 1];
}

시간 / 공간 복잡도

시간 복잡도: O(n log n)
공간 복잡도: O(n)

풀이 2

아이디어

정렬할 필요 없이 t에 있는 문자들의 아스키 코드 값을 모두 더한 뒤에 s에 있는 문자들의 아스키 코드 값을 모두 빼주면 s에는 없는 문자의 아스키 코드 값이 남게 된다. 그 값을 다시 문자로 변환해서 반환하면 된다.

코드

function findTheDifference(s: string, t: string): string {
  let diff = 0;

  for (const c of t) diff += c.charCodeAt(0);
  for (const c of s) diff -= c.charCodeAt(0);

  return String.fromCharCode(diff);
}

시간 / 공간 복잡도

시간 복잡도: O(n)
공간 복잡도: O(1)

Back