단어 나누기 (feat. 백준, 1251번)

단어 나누기
https://www.acmicpc.net/problem/1251

1251번: 단어 나누기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	string str, t1, t2, t3;
	cin >> str;
	register int size = str.size();
	set<string> ans;
	for (register int i = 1, j, k; i < size; ++i)
		for (j = 1; j < size - i; ++j) {
			k = size - (i + j);
			t1 = str.substr(0, i);
			t2 = str.substr(i, j);
			t3 = str.substr(i + j, k);
			reverse(t1.begin(), t1.end());
			reverse(t2.begin(), t2.end());
			reverse(t3.begin(), t3.end());
			ans.insert(t1 + t2 + t3);
		}
	cout << *ans.begin();
	return 0;
}
// *&)*@*

 

 

1. 단어를 하나 이상으로 세개의 문자열로 쪼갰을때의 모든 경우에 대해서 구하고, 그중 사전순 첫번째 문자열을 출력하는 문제입니다.
   가령 abcd 4개의 문자라면 1/1/2, 1/2/1, 2/1/1 로 쪼갠 3개의 문자열 중 가장 사전순 첫번째 문자열을 출력합니다.
2. 따라서 3개의 문자열에 대한 i, j, k 로 완전탐색하여 저장한 뒤, 자료구조 set 특성상 첫 문자열을 출력합니다.