백준(BOJ) 16925번 문자열 추측

문제 :

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

16925번: 문자열 추측

 

풀이 :

 

좀 더 나은 간단한 풀이가 있겠지만 일단 처음 떠올랐던 그대로 풀이를 작성하겠다.

 

예제 1번 ) 5 ba a abab a aba baba ab aba 으로 설명해보자면

 

우선 크기로 정렬 시 a a ab ba aba aba abab baba 가 나오게 된다.

                                   (1)(2)                               (3)     (4)

 

이때 정답이 되는 문자는  (1) + (3) , (1) + (4) , (2) + (3), (2) + (4) 후보들 중 하나가 될 것이다.

 

따라서 네 가지 경우중 답이 된다면 바로 출력 후 종료해주자.

 

후보들을 골랐다면 indexes를 통해 속해있는 문자열에 시작 인덱스들을 모두 찾아주는(Find) 배열을 만든다.

 

2 * n -2 동안 prefix 거나 ( string.find 했을 시 0이 나오는 경우 )

 

suffix 거나 ( 0이 아니라면 indexes를 통해 나온 가장 나중 인덱스 + 현재 cur의 합이 n이 됐을 때 suffix이다)

 

cand = ababa에 cur = ba에 대한 suffix 예)

ba는 Find시 두 번 속하고 1과 3이 나오게 된다. 이때 가장 나중에 나온 숫자인 3 그리고 ba의 크기 2

를 더할 시 ababa에 사이즈가 나오므로 suffix이다.

 

 

모두 prefix 거나 suffix가 나온다면 P인지 S인지 적어주자. 이미 P가 나왔다면

 

그다음은 S이므로 set을 통해 처리해주었다.

 

 

코드 ( C++ )

	#include <iostream>
	#include <vector>
	#include <string>
	#include <algorithm>
	#include <unordered_set>
	using namespace std;
	bool compare(string a, string b) {
	return a.size() < b.size();
	}
	vector<int> Find(string a, string b) {
	vector<int> temp;
	for (int i = 0; i <= a.size() - b.size(); ++i) {
	int impos = 0;
	for (int j = 0; j < b.size(); ++j) {
	if (a[i + j] != b[j]) {
	impos = 1;
	break;
	}
	}
	if (!impos) {
	temp.push_back(i);
	}
	}
	return temp;
	}
	int main()
	{
	int n;
	cin >> n;
	vector<string> pres;
	for (int i = 0; i < 2 * n - 2; ++i) {
	string s; cin >> s;
	pres.push_back(s);
	}
	vector<string> cur(pres);
	sort(pres.begin(), pres.end(), compare);
	vector<string> cands;
	cands.push_back(pres[0] + pres[pres.size() - 2]);
	cands.push_back(pres[0] + pres[pres.size() - 1]);
	cands.push_back(pres[1] + pres[pres.size() - 2]);
	cands.push_back(pres[1] + pres[pres.size() - 1]);
	for (int i = 0; i < 4; ++i) {
	string cand = cands[i];
	int impos = 0;
	bool jump = 0;
	for (int i = 0; i < 2 * n - 2; ++i) {
	vector<int> indexes = Find(cand, cur[i]);
	if (indexes.size() == 0) {
	jump = 1;
	break;
	}
	int num = indexes[indexes.size() - 1];
	if (cand.find(cur[i]) == 0 || (cand.find(cur[i]) != -1 && num +
	cur[i].size() == n));
	else {
	impos = 1;
	break;
	}
	}
	if (jump) continue;
	if (impos) continue;
	cout << cand << "\n";
	unordered_set<string> se;
	for (int i = 0; i < 2 * n - 2; ++i) {
	if (cand.find(cur[i]) == 0 && se.count(cur[i]) == 0) {
	cout << 'P';
	se.insert(cur[i]);
	}
	else
	cout << 'S';
	}
	cout << "\n";
	return 0;
	}
	}

view raw .cpp hosted with ❤ by GitHub