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

C++로 풀어보는 문자 산술 퍼즐: SEND + MORE = MONEY

문제 소개

왼쪽 항이 단어들로, 오른쪽 항이 결과 단어로 표현된 방정식이 있다고 가정해 봅시다. 우리는 다음 규칙을 모두 만족하면서 이 방정식이 성립할 수 있는지, 즉 '풀 수 있는지'를 판단해야 합니다.

  • 각 문자는 정확히 한 자리 숫자(0~9)로 치환됩니다.
  • 서로 다른 두 문자는 반드시 서로 다른 숫자에 대응되어야 합니다.
  • 각 단어(words[i])와 결과(result)는 선행 0(leading zero)이 없는 수로 해석됩니다.
  • 왼쪽에 있는 수들의 합은 오른쪽의 수와 정확히 같아야 합니다.

예시로 이해하기

예를 들어 words = ["SEND", "MORE"], result = "MONEY"가 입력으로 주어진다면 출력은 True입니다. 알파벳을 다음과 같이 매핑하면 방정식이 성립하기 때문입니다.

S→9, E→5, N→6, D→7, M→1, O→0, R→8, Y→2

이 매핑을 적용하면 "SEND" + "MORE" = "MONEY"는 실제로 9567 + 1085 = 10652와 동일합니다.

풀이 전략: 백트래킹

이 문제는 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 핵심 자료구조는 다음과 같습니다.

  • i2c[10]: 숫자 i에 대응되는 문자 인덱스를 저장 (미사용 시 -1)
  • c2i[26]: 알파벳 문자에 대응되는 숫자를 저장 (미사용 시 -1)
  • w: 단어 목록, r: 결과 문자열

solve(idx, l, sum) 함수는 idx번째 단어의 l번째 자릿수를 처리하며, 지금까지의 자릿수 합을 sum으로 유지합니다. 모든 단어의 현재 자릿수를 더한 뒤에는 결과 문자열의 해당 자릿수와 올림수(carry)를 검사하고, 새로운 매핑을 시도했다가 실패하면 원상복구하여 다른 경우를 탐색합니다.

알고리즘 상세 단계

  1. solve() 함수는 idx, l, sum 세 개의 매개변수를 받습니다.
  2. l이 결과 문자열 r의 길이와 같다면, sum이 0일 때만 true를 반환합니다(모든 자릿수 처리 완료).
  3. idx가 단어 개수와 같다면(모든 단어의 현재 자릿수 처리 완료):
    • r[l]에 이미 숫자가 배정되어 있다면, 그 값이 sum % 10과 일치할 때만 다음 자릿수로 진행합니다.
    • 배정되어 있지 않다면 sum % 10을 새로 배정합니다. 단, 최고 자릿수에서 0이 되면 선행 0 금지 규칙에 위배되므로 false를 반환합니다.
  4. 현재 단어 w[idx]의 길이가 l 이하라면 다음 단어로 넘어갑니다.
  5. w[idx][l]에 이미 숫자가 배정되어 있다면(마지막 자릿수가 0인 경우는 제외), 그 값을 sum에 더해 진행합니다.
  6. 그렇지 않다면 0부터 9까지의 숫자를 하나씩 시도하며 재귀 호출합니다. 이미 사용 중인 숫자와, 단어의 마지막 자릿수에 배정되려는 0은 건너뜁니다.

메인 함수 처리 과정

  1. i2c와 c2i 배열을 -1로 초기화합니다.
  2. result와 각 words[i]를 뒤집어 1의 자리부터 계산할 수 있도록 준비합니다.
  3. 어떤 단어의 길이가 result보다 길다면 애초에 성립할 수 없으므로 false를 반환합니다.
  4. solve(0, 0, 0)을 호출한 결과를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   char i2c[10];
   int c2i[26];
   vector<string> w;
   string r;
   bool solve(int idx, int l, int sum){
      if (l == r.size()) {
         return sum == 0;
      }
      if (idx == w.size()) {
         if (c2i[r[l] - 'A'] != -1) {
            if (c2i[r[l] - 'A'] == sum % 10) {
               return solve(0, l + 1, sum / 10);
            }
         }
         else if (i2c[sum % 10] == -1) {
            if (l == r.size() - 1 && sum % 10 == 0)
            return false;
            c2i[r[l] - 'A'] = sum % 10;
            i2c[sum % 10] = r[l] - 'A';
            bool temp = solve(0, l + 1, sum / 10);
            c2i[r[l] - 'A'] = -1;
            i2c[sum % 10] = -1;
            return temp;
         }
         return false;
      }
      if (l >= w[idx].size()) {
         return solve(idx + 1, l, sum);
      }
      if (c2i[w[idx][l] - 'A'] != -1) {
         if (l == w[idx].size() - 1 && c2i[w[idx][l] - 'A'] == 0){
            return false;
         }
         return solve(idx + 1, l, sum + c2i[w[idx][l] - 'A']);
      }
      for (int i = 0; i < 10; i++) {
         if (i2c[i] != -1)
         continue;
         if (i == 0 && l == w[idx].size() - 1)
         continue;
         i2c[i] = w[idx][l] - 'A';
         c2i[w[idx][l] - 'A'] = i;
         bool temp = solve(idx + 1, l, sum + i);
         i2c[i] = -1;
         c2i[w[idx][l] - 'A'] = -1;
         if (temp)
         return true;
      }
      return false;
   }
   bool isSolvable(vector<string>& words, string result){
      memset(i2c, -1, sizeof(i2c));
      memset(c2i, -1, sizeof(c2i));
      reverse(result.begin(), result.end());
      for (int i = 0; i < words.size(); i++) {
         if (words[i].size() > result.size())
         return false;
         reverse(words[i].begin(), words[i].end());
      }
      r = result;
      w = words;
      return solve(0, 0, 0);
   }
};
main(){
   Solution ob;
   vector<string> v = {"SEND","MORE"};
   cout << (ob.isSolvable(v, "MONEY"));
}

입력

{"SEND","MORE"}, "MONEY"

출력

1

마무리

이 풀이는 각 미배정 문자에 대해 최대 10가지 숫자를 시도하는 완전 탐색 기반 백트래킹입니다. 불가능한 경우를 조기에 잘라내는 가지치기(선행 0 검사, 이미 배정된 숫자 재사용 등) 덕분에 실제 탐색 공간은 크게 줄어들어, 알파벳 종류가 최대 10개로 제한되는 이 문제를 충분히 빠르게 해결할 수 있습니다.