백준 16925번 문자열 추측 C++

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

 

1. 문자열들을 입력받아서 길이가 긴 게 앞에 오도록 정렬한다.

2. 맨 앞에 있는 2개의 문자열의 길이가 제일 길다. 하나를 a, 다른 하나를 b라고 한다.

3. a가 접두사라고 가정했을 때는 a 에 b의 마지막 문자를 붙여 완전한 문자열을 만든다. (b가 접두사라고 가정했을 때는 반대로)

4. 3에서 구한 완전한 문자열 두가지 경우에 대해서 나머지 문자열들도 검사를 해서 맞는 경우가 정답이다. (둘 다 맞으면 아무거나)

 

#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>

using namespace std;
typedef long long ll;

int n;
pair<int, int> offset[2] = { {0,1},{1,0} };
bool compare(const pair<int, string>& lhs, const pair<int, string>& rhs) {
	return lhs.second.length() > rhs.second.length();
}

bool isPossible(string FullStr, const vector<pair<int, string>>& strs) {
	vector<bool> isPrefix((n - 1) * 2);
	for (int i = 0; i < n - 1; i++) {
		int idx = i * 2;
		bool ispossible = false;
		string prefix = FullStr.substr(0, n - i - 1);
		string suffix = FullStr.substr(i + 1, n - i);
		for (int j = 0; j < 2; j++) {
			string str1 = strs[idx + offset[j].first].second;
			string str2 = strs[idx + offset[j].second].second;
			bool isprefix = true;
			bool issuffix = true;
			if (str1 != prefix) isprefix = false;
			if (str2 != suffix) issuffix = false;
			if (isprefix && issuffix) {
				isPrefix[strs[idx + offset[j].first].first] = true;
				isPrefix[strs[idx + offset[j].second].first] = false;
				ispossible = true;
				break;
			}
		}
		if (!ispossible) return false;
	}
	cout << FullStr << "\n";
	for (int i = 0; i < (n - 1) * 2; i++) {
		if (isPrefix[i]) cout << 'P';
		else cout << 'S';
	}
	return true;
}

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

	cin >> n;
	vector<pair<int, string>> strs((n - 1) * 2);

	for (int i = 0; i < (n - 1) * 2; i++) {
		string str;
		cin >> str;
		strs[i] = { i,str };
	}

	sort(strs.begin(), strs.end(), compare);

	for (int i = 0; i < 2; i++) {
		string biggestStr = strs[i].second;
		string otherBiggestStr = strs[(i + 1) % 2].second;

		string tmpFullStr = biggestStr + otherBiggestStr[n - 2];
		if (isPossible(tmpFullStr, strs)) {
			break;	
		}
	}
};