백준 15811 (복면산) c++

문제

15811번: 복면산?!

18자리 이하인 영어 대문자 문자열 3개가 주어지는데

첫번째와 두번째로 주어진 영어 대문자에 서로 겹치지 않는 숫자를 집어넣어 그 둘을 합친게

세번째로 주어진 문자열과 동일하면 YES를 출력하고 그렇지 않으면 NO를 출력하는 문제입니다.

예를 들어 문자열이 SUN FUN SWIM 이라고 주어지면

SUN = 067

FUN = 867

라는 숫자를 대입할 수 있습니다. 그 둘을 합치면

SWIM = 0934 이렇게 값이 일치하는 것을 볼 수 있습니다.

각 알파벳에는 숫자가 0 ~ 9 까지의 숫자중 1개만 들어갈 수 있고 절대 겹치지 말아야 합니다.

 

저는 처음에 이렇게 3가지로 구현을 해야한다는 생각이 들었습니다.

1. 알파벳에 따른 값 저장 어캐?

2. 알파벳에 값을 0 ~ 9 어캐 분배?

3. 알파벳에 중복값 체크?

하지만 구현에 어려움이 생겨 다른분들이 만들었던 코드를 보고 아이디어를 얻어 풀어봤습니다.

먼저 사용할 배열들과 변수 들입니다.

str[3] = 입력받을 문자열들입니다.

alphabet_check[26]=입력 받은 문자열들중에 서로 중복되지않은 알파벳이 몇개 있는 지

체크해주는 bool 형 배열입니다.

num_check[10] = 나중에 각 알파벳 마다 숫자를 분배해 줄건데 서로 중복되지 않게 체크해주는 bool 형 배열입니다.

v[] = alphabet_check에서 true인 값들의 인덱스를 저장할 것입니다. 나중에 알파벳 값을 숫자로 인식하기 위함입니다.

alphabet[26] = 알파벳에 값을 넣어줄 배열입니다. 예를들어 A는 인덱스가 0이므로 alphabet[0] = ? 가 됩니다.

물음표에는 분배할 숫자에 따라 여러가지 값이 들어갈 수 있습니다.

sum[3] = 각 문자열 마다 수가 들어갑니다. 예를들어 첫번째 문자열 SUN = 067 이라면 

sum[0] = 67 입니다.

flag = 조건에 만족했을시 flag = true를 설정하고 YES를 출력합니다.

---

각각의 문자열을 입력 받고 어떤 알파벳이 들어왔는지 체크해주는 단계 입니다.

4번째 줄을 보시면 str[i][j] - 'A'  각각의 문자에 대해 인덱스 값을 주는 단계 입니다. 

EX) A = 0, B = 1, C = 2 ......... X = 23, Y = 24, Z = 25

---

alphabet_check에 true로된 위치의 인덱스를 v 벡터에 넣어줍니다.

7번째 줄을 보면 v.size()가 10이하가 되어야만 recursion함수를 수행할 수 있습니다.

왜냐하면 각 알파벳 마다 숫자를 분배해야하는데 분배 가능한 숫자는  0~ 9 총 10개의 수 이므로 

10이 넘어가 버리면 중복되지않은 알파벳이 10개보다 많다는 의미이기 때문입니다.

---

이제 알파벳에 숫자를 분배하고 알파벳에 따른 값을 저장할 것입니다.

recursion 함수는 idx라는 변수를 매개변수로 받습니다. idx는 v 벡터의 인덱스라고 생각하면 됩니다.

 

먼저 16번째 줄 else문 부터 보면 이제 각 알파벳 마다 서로 다른 수를 분배해 줄것입니다.

18번째 줄 = num_check[i]가 false란 의미는 현재 i는 아직 분배된 수중에서 안겹친다는 의미입니다.

따라서 이제 i를 알파벳에 분배를 해줄것입니다.

20번째 줄을 보면 alphabet[v[idx] = i 란 의미는 alphabet에 i값을 분배해준것입니다.

예를 들어 alphabet[A] = alphabet[0] = i => A = i 라는 의미입니다.

이미 벡터 v에는 알파벳의 인덱스값이 들어가 있으므로 v[idx]에 해당하는 알파벳 인덱스에 i값을 넣어주는것과 동일합니다.

21번째 줄을 보면 재귀함수이므로 idx+1의 값을 매개변수로 넣고 실행해 줍니다.

22, 23번째 줄을 보면 만약 조건에 맞지 않으면 다시 해야하므로 num_check와 alphabet 배열의 값을 원래 상태로

되돌려 놓습니다.

 

이제 3번째 줄을 보면 idx = v.size() 란 의미는 각각의 알파벳에 서로다른 숫자를 분배했다는 의미이므로

확인을 해봐야 합니다.

sum에 다가 각 알파벳의 해당하는 숫자를 불러와 값을 저장해줍니다.

11번째 줄을 보면 이제 확인하는 단계 입니다.

---

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
using namespace std;
using ll = long long;
using ull = unsigned long long;
string str[3];
bool alphabet_check[26];
bool num_check[10];
vector<int>v;
int alphabet[26];
int sum[3];
bool flag=false;
void recursion(int idx);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    for (int i = 0; i < 3; i++) {
        cin >> str[i]; 
        for (int j = 0; j < str[i].size(); j++)
            alphabet_check[str[i][j] - 'A'] = true;    
    }
    for (int i = 0; i < 26; i++) {
        if (alphabet_check[i]) {
            v.push_back(i);
        }
    }
 
    if (v.size() <= 10)
        recursion(0);
 
    if (flag)cout << "YES";
    else cout << "NO";
    return 0;
}
void recursion(int idx) {
    if (flag)return;
    if (idx == v.size()) {
        for (int i = 0; i < 3; i++) {
            sum[i] = 0;
            for (int j = 0; j < str[i].size(); j++) {
                sum[i] *= 10;
                sum[i] += alphabet[str[i][j] - 'A'];
            }
        }
        if (sum[0] + sum[1] == sum[2]) {
            flag = true;
            return;
        }
    }
    else {
        for (int i = 0; i < 10; i++) {
            if (!num_check[i]) {
                num_check[i] = true;
                alphabet[v[idx]] = i;
                recursion(idx + 1);
                num_check[i] = false;
                alphabet[v[idx]] = 0;
            }
        }
    }
}