C++로 두 문자열의 차이 찾기 – 추가된 문자 구하는 방법

소문자로만 구성된 두 문자열 s와 t가 있다고 가정해 보겠습니다. 문자열 t는 문자열 s를 무작위로 섞은 뒤, 임의의 위치에 한 글자를 추가하여 생성됩니다. 우리가 해야 할 일은 바로 t에 새롭게 추가된 그 문자를 찾아내는 것입니다.

예를 들어 입력이 "mnopq", "pqmnot"라면 출력은 "t"가 됩니다. 이 't'가 바로 추가된 문자입니다.

해결 접근 방법

이 문제는 아스키(ASCII) 코드 값의 합을 활용하면 매우 효율적으로 해결할 수 있습니다. 문자마다 고유한 아스키 코드 값이 존재한다는 점을 이용하여, 두 문자열의 전체 합을 비교하는 것입니다. 시간 복잡도는 O(n + m), 공간 복잡도는 O(1)로 매우 효율적입니다.

구체적인 풀이 단계는 다음과 같습니다.

sSum = 0, tSum = 0으로 초기화합니다.
반복문을 돌며 문자열 s의 각 문자 아스키 값을 sSum에 누적합니다.
같은 방식으로 문자열 t의 각 문자 아스키 값을 tSum에 누적합니다.
(tSum − sSum)의 차이를 char 타입으로 변환하여 반환합니다. 이 값이 곧 추가된 문자입니다.

s와 t는 같은 문자들로 구성되어 있되 하나의 문자만 추가된 상태이므로, 두 합의 차이는 정확히 추가된 문자 하나의 아스키 값과 일치하게 됩니다.

C++ 구현 예제

더 쉽게 이해할 수 있도록 다음 C++ 구현 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   char findTheDifference(string s, string t) {
      int sSum = 0;
      int tSum = 0;
      for (int i = 0; i < s.length(); i++) {
         sSum += s[i];
      }
      for (int j = 0; j < t.length(); j++) {
         tSum += t[j];
      }
      return char(tSum - sSum);
   }
};
main(){
   Solution ob;
   cout << (ob.findTheDifference("mnopq","pqmnot"));
}

입력

"mnopq","pqmnot"

출력

위 코드에서 findTheDifference 함수는 두 문자열의 아스키 합을 각각 계산한 후, 그 차이를 문자로 반환합니다. 실행 결과로 't'가 출력되며, 이는 문자열 t에 추가된 문자임을 확인할 수 있습니다.