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

C++로 해결하는 단어 패턴 II(Word Pattern II) 문제 완벽 가이드

패턴(pattern)과 문자열 str이 주어졌을 때, str이 해당 패턴을 따르는지 확인해야 합니다. 여기서 '패턴을 따른다'는 것은 완전 일치(full match)를 의미하며, 패턴의 각 문자와 str의 비어 있지 않은 부분 문자열 사이에 전단사(bijection), 즉 일대일 대응 관계가 성립해야 합니다.

예를 들어 패턴이 "abaa"이고 str이 "orangegreenorangeorange"라면 결과는 true입니다. 'a'는 "orange"에, 'b'는 "green"에 각각 대응되어 전체 문자열이 패턴과 정확히 일치하기 때문입니다.

문제 해결 접근 방법

이 문제는 백트래킹(backtracking) 기법을 활용한 재귀 함수로 해결할 수 있습니다. 핵심 아이디어는 패턴의 각 문자에 대해 가능한 모든 부분 문자열을 시도해 보되, 이미 만들어진 매핑과 충돌하지 않는 경우에만 탐색을 진행하는 것입니다.

solve()라는 재귀 함수를 정의합니다. 이 함수는 시작 인덱스 i와 j, 패턴 ptr, 문자열 s, 문자-문자열 맵 m, 이미 사용된 문자열의 집합 used를 매개변수로 받습니다.

알고리즘 단계

  1. 성공 종료 조건: i가 s의 길이 이상이고 동시에 j가 ptr의 길이 이상이면, 두 문자열을 모두 소진한 것이므로 true를 반환합니다.
  2. 실패 종료 조건: i가 s의 길이 이상이거나 j가 ptr의 길이 이상이면 어느 한쪽만 처리가 끝난 상태이므로 false를 반환합니다.
  3. 이미 매핑된 문자인 경우: ptr[j]가 맵 m에 존재한다면
    • req = m[ptr[j]]로 설정하고, req의 길이를 len이라 합니다.
    • len이 남은 문자열 길이보다 크면 false를 반환합니다.
    • s의 현재 위치에서 len 길이만큼의 부분 문자열이 req와 일치하고, solve(i + len, j + 1, ...)의 결과가 true이면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.
  4. 아직 매핑되지 않은 문자인 경우: x = ptr[j]로 설정한 뒤, k를 i부터 s의 끝까지 하나씩 증가시키며 반복합니다.
    • temp를 s의 i번째부터 k번째까지의 부분 문자열로 만듭니다.
    • temp가 이미 used 집합에 존재하면 전단사 조건에 위배되므로 다음 반복으로 건너뜁니다.
    • m[x] = temp로 매핑을 설정하고 used에 temp를 추가한 후 재귀 호출합니다.
    • 재귀 호출이 true를 반환하면 곧바로 true를 반환하고, 그렇지 않으면 매핑을 되돌립니다(m에서 x 삭제, used에서 temp 삭제). 이것이 바로 백트래킹 과정입니다.
  5. 모든 경우를 시도해도 성공하지 못하면 false를 반환합니다.

메인 메서드 구현

메인 메서드에서는 빈 맵 m과 빈 집합 used를 생성한 후, solve(0, 0, ptr, s, m, used)를 호출하여 최종 결과를 얻습니다.

예시 코드

아래의 실제 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool solve(int i, int j, string ptr, string s, map <char, string>& m, set<string>& used){
      if (i >= s.size() && j >= ptr.size()) {
         return true;
      }
      if (i >= s.size() || j >= ptr.size())
         return false;
      if (m.count(ptr[j])) {
         string req = m[ptr[j]];
         int len = req.size();
         if (len > s.size() - i)
            return false;
         if ((s.substr(i, len) == req) && solve(i + len, j + 1, ptr, s, m, used))
            return true;
         return false;
      }
      else {
         char x = ptr[j];
         for (int k = i; k < s.size(); k++) {
            string temp = s.substr(i, k - i + 1);
            ;
            if (used.count(temp))
               continue;
            m[x] = temp;
            used.insert(temp);
            if (solve(k + 1, j + 1, ptr, s, m, used))
               return true;
            m.erase(x);
            used.erase(temp);
         }
      }
      return false;
   }
   bool wordPatternMatch(string ptr, string s) {
      map<char, string> m;
      set<string> used;
      return solve(0, 0, ptr, s, m, used);
   }
};
main(){
   Solution ob;
   cout << (ob.wordPatternMatch("abaa", "orangegreenorangeorange"));
}

입력

"abaa" "orangegreenorangeorange"

출력

1

출력값 1(true)은 패턴 "abaa"가 문자열 "orangegreenorangeorange"와 일치함을 의미합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 지수형으로, 최악의 경우 문자열 길이 n과 패턴 길이 m에 대해 O(n^m) 수준입니다. 다만 used 집합을 통한 중복 제거와 매핑 충돌 검증 덕분에 불필요한 탐색 가지를 상당 부분 가지치기(pruning)할 수 있어 실제 실행 속도는 훨씬 빠릅니다.