Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 두 문자열이 동형(Isomorphic)인지 판별하는 방법

두 개의 문자열 s와 t가 주어졌을 때, 이 두 문자열이 동형(isomorphic)인지 확인하는 문제를 살펴보겠습니다.

동형 문자열이란?

동형 문자열이란 s에 포함된 문자들을 다른 문자로 치환했을 때 t를 만들 수 있는 경우를 의미합니다. 단, 치환 과정에서 다음 규칙을 반드시 지켜야 합니다.

  • 모든 문자는 순서를 유지한 채 일관되게 치환되어야 합니다. 즉, 한 번 치환된 문자는 이후에도 항상 같은 문자로 치환되어야 합니다.
  • 서로 다른 두 문자가 같은 문자로 매핑될 수는 없습니다.
  • 반면, 한 문자는 자기 자신으로 매핑되는 것이 허용됩니다.

예를 들어 입력이 s = "egg", t = "add"라고 가정해 보겠습니다. 이 경우 'e' → 'a', 'g' → 'd'로 매핑할 수 있으므로 결과는 true입니다.

해결 알고리즘

이 문제는 방문 여부를 기록하는 배열과 문자 간 매핑 정보를 저장하는 배열을 활용하여 해결할 수 있습니다. 단계별 풀이 과정은 다음과 같습니다.

  1. 크기 256의 배열 arr을 선언하고 모든 값을 -1로 초기화합니다. (매핑 정보 저장용)
  2. 크기 256의 배열 visited를 선언하고 0으로 초기화합니다. (s의 문자 방문 여부)
  3. 크기 256의 배열 visited1을 선언하고 0으로 초기화합니다. (t의 문자 방문 여부)
  4. i := 0부터 s의 길이까지 반복하면서 다음을 수행합니다.
    • 만약 visited[s[i]]가 1이거나 visited1[t[i]]가 1이라면:
      • arr[s[i]]가 t[i] - 'a'(ASCII 연산)와 같지 않으면 false를 반환합니다. 즉, 이미 정해진 매핑과 현재 매핑이 충돌한다는 뜻입니다.
    • 그렇지 않다면(처음 만나는 문자 쌍이라면):
      • visited[s[i]] := 1
      • visited1[t[i]] := 1
      • arr[s[i]] := t[i] - 'a' 로 새로운 매핑을 등록합니다.
  5. 모든 문자를 문제없이 처리했다면 true를 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 구현 방법을 더 쉽게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool isIsomorphic(string s, string t) {
      vector<int> arr(256, -1);
      vector<bool> visited(256, 0);
      vector<bool> visited1(256, 0);
      for (int i = 0; i < s.length(); i++) {
         if (visited[s[i]] == 1 || visited1[t[i]] == 1) {
            if (arr[s[i]] != t[i] - 'a') {
               return false;
            }
         }
         else {
            visited[s[i]] = 1;
            visited1[t[i]] = 1;
            arr[s[i]] = t[i] - 'a';
         }
      }
      return true;
   }
};
main(){
   Solution ob;
   cout << (ob.isIsomorphic("sky","fry"));
}

입력

"sky","fry"

출력

1

위 예제에서 "sky"와 "fry"는 's' → 'f', 'k' → 'r', 'y' → 'y'로 일관되게 매핑되므로 동형 문자열이며, 결과로 1(true)이 출력됩니다. 이 알고리즘은 문자열의 길이 n에 대해 O(n)의 시간 복잡도로 동작하므로 매우 효율적입니다.