백준 1099번 알 수 없는 문장 C++

출처 : https://www.acmicpc.net/problem/1099

 

1. 문장을 순회하면서 각각의 단어마다 현재 인덱스 - 단어의 크기 + 1 부터 현재 인덱스까지의 구성된 문자가 단어와 같은지 확인한다.

ex) 현재 인덱스가 2이고, 단어가 "one" 이라고 하면 2 - 3 + 1 = 0 부터 2 까지 구성된 문자는 n, e, o 이고 이는 "one"과 구성된 문자가 같다.

 

2. 1에서 구한 인덱스 - 단어의 크기 + 1 이 0보다 작거나 구성된 문자가 같지 않다면 다음 문자를 검색한다.

1에서 구성된 문자가 같다면 순서를 바꾸는 비용을 구하고 dp로 해결할 수 있다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

bool operator==(const map<char, int>& lhs, const map<char, int>& rhs) {
	if (lhs.size() != rhs.size()) return false;
	auto it1 = lhs.begin();
	auto it2 = rhs.begin();
	bool ret = true;
	while (true) {
		if (it1 == lhs.end() || it2 == rhs.end()) break;
		if (it1->first == it2->first && it1->second == it2->second) {
			++it1;
			++it2;
		}
		else {
			ret = false;
			break;
		}
	}
	return ret;
}

int GetPrice(const string& comp, const string& target) {
	int ret = 0;
	for (int i = 0; i < comp.length(); i++) {
		if (comp[i] != target[i]) ret++;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string target;
	cin >> target;
	int n;
	cin >> n;
	vector<string> v(n);
	vector<map<char, int>> m(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		for (int j = 0; j < v[i].length(); j++) {
			m[i][v[i][j]]++;
		}
	}
	vector<int> dp(target.length(), -1);
	for (int i = 0; i < target.length(); i++) {
		for (int j = 0; j < n; j++) {
			int start = i - v[j].length() + 1;
			if (start < 0) continue;
			map<char, int> tmp_map;
			for (int k = start; k <= i; k++) {
				tmp_map[target[k]]++;
			}
			if (m[j] == tmp_map) {
				int price = GetPrice(target.substr(start, v[j].length()), v[j]);
				if (start == 0) {
					if (dp[i] == -1) dp[i] = price;
					else dp[i] = min(dp[i], price);
				}
				else {
					if (dp[start - 1] == -1) continue;
					else {
						if (dp[i] == -1) dp[i] = dp[start - 1] + price;
						else dp[i] = min(dp[i], dp[start - 1] + price);
					}
				}
			}
		}
	}
	cout << dp[target.length() - 1];
};