C++로 문자열이 주어진 패턴을 따르는지 확인하는 프로그램 작성 방법

문제 개요

패턴 p와 문자열 str이 주어졌을 때, str이 해당 패턴을 정확히 따르는지 확인하는 프로그램을 만들어 보겠습니다. 여기서 "패턴을 따른다"는 것은 패턴의 각 문자와 문자열 내 비어 있지 않은 단어 사이에 전단사(bijection), 즉 일대일 대응 관계가 성립한다는 의미입니다.

예를 들어 패턴이 "cbbc"이고 문자열이 "word pattern pattern word"라면 결과는 True(1)입니다. 첫 번째 문자 'c'는 "word"에, 두 번째 문자 'b'는 "pattern"에 각각 일관되게 대응되기 때문입니다.

해결 전략

핵심 아이디어는 패턴과 단어열을 각각 정규화(normalization)하여 동일한 형식의 코드 문자열로 변환한 뒤, 두 결과를 직접 비교하는 것입니다. 진행 단계는 다음과 같습니다.

1. 문자열 str을 공백을 기준으로 분리해 단어 배열 words를 생성합니다.
2. 패턴의 각 문자에 대해 해시맵 p2i를 이용해 처음 등장한 순서대로 번호를 부여하고, 이를 이어 붙여 문자열 pat을 만듭니다.
3. 단어 배열의 각 단어에 대해서도 해시맵 str2i로 동일한 방식을 적용해 문자열 pat1을 만듭니다.
4. pat과 pat1이 완전히 같으면 true, 다르면 false를 반환합니다.

이 방식은 양방향 대응 관계를 명시적으로 검사하지 않고도 전단사 조건을 자연스럽게 확인할 수 있습니다. 서로 다른 문자가 같은 단어에 대응하거나, 서로 다른 단어가 같은 문자에 대응하는 경우 변환된 코드 문자열이 달라지기 때문입니다.

C++ 구현 예제

다음 코드를 통해 실제 구현 과정을 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool wordPattern( string pattern, string str ) {
      istringstream strcin(str);
      string word;
      vector<string> words;
      while (strcin >> word)
         words.push_back(word);
      unordered_map<char, int> p2i;
      int i = 0;
      string pat = "";
      for (auto c : pattern) {
         if (p2i.count(c) == 0) {
            i++;
            p2i[c] = i;
         }
         pat += to_string(p2i[c]);
      }
      unordered_map<string, int> str2i;
      i = 0;
      string pat1 = "";
      for (auto c : words) {
         if (str2i.count(c) == 0) {
            i++;
            str2i[c] = i;
         }
         pat1 += to_string(str2i[c]);
      }
      return pat1 == pat;
   }
};
main(){
   Solution ob;
   cout << (ob.wordPattern("cbbc", "word pattern pattern word"));
}

입력

"cbbc", "word pattern pattern word"

출력

1

출력값 1은 bool 타입의 true가 정수로 변환된 결과로, 주어진 문자열이 패턴을 정확히 따른다는 것을 의미합니다.

복잡도 분석

시간 복잡도는 패턴 길이 N과 문자열의 총 길이 M에 비례하여 O(N + M)입니다. 공간 복잡도 역시 해시맵과 변환된 문자열을 저장해야 하므로 O(N + M)입니다. 입력 크기에 선형으로 증가하므로 매우 효율적인 해결 방법이라 할 수 있습니다.