[알고리즘문제] 백준 단어나누기

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

1251번: 단어 나누기

 

단어를 3분할 하여 분할된 단어를 각각 reverse하여, 합친 후 사전순으로 가장 빠른 단어가 될 경우를 return 시켜야 된다.

자른 문자열의 길이가 최소 1이상이 되어야 한다.

주어진 input이 mobitel일 경우 mob, ite, l을 각각 reverse 하면 bom, eti, l가 나오는데 합치면 bometil이 되며 이 단어는 만들 수 있는 단어 중 사전순으로 가장 빠르다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

string sub(string s, int pos1, int pos2, int add) {
	string s1 = s.substr(0, pos1 + 1);
	string s2 = s.substr(pos1 + 1, pos2);
	pos2 += add;
	string s3 = s.substr(pos2 + 1);

	reverse(s1.begin(), s1.end());
	reverse(s2.begin(), s2.end());
	reverse(s3.begin(), s3.end());

	return s1 + s2 + s3;
}

string solution(string s) {
	vector<string> v = { "","" };

	v[0] = sub(s, 0, 1, 0);
	for (int i = 0; i < s.size() - 2; i++) {
		for (int j = 1; j < s.size() - 1; j++) {
			if (j + i >= s.size() - 1) continue;
			v[1] = sub(s, i, j, i);
			sort(v.begin(), v.end());
		}
	}
	return v[0];
}

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

	string s = "";
	cin >> s;
	cout << solution(s) << "\n";
	
	return 0;
}

모든 경우의 수를 찾아본 후 가장 빠른  단어를 return한다.

input이 mobitel일때 

m, o, letib
m, o, letib
m, bo, leti
m, ibo, let
m, tibo, le
m, etibo, l
om, b, leti
om, ib, let
om, tib, le
om, etib, l
bom, i, let
bom, ti, le
bom, eti, l
ibom, t, le
ibom, et, l
tibom, e, l

여기서 사전 순 가장빠른 단어는 "bometil"가 된다.

 

time-complexity : O(n²)

space-complexity : O(n)