[Algorithm]BOJ 1251

1251번

• 주어진 단어를 세 구역으로 나누고

• 그 구역들을 reverse 시키고

• 합친 문자열 중에

• 가장 사전순으로 앞쪽에 오는 문자열을 출력하는 문제

• 예제

  • 입력 : mobitel
  • 출력 : bometil
  • 입력을 다음과 같이 쪼개면 가능
    • mob/ ite/ l
    • → bom/ eti / l
    • bometil

• 문자열이 다 섞여있기 때문에 직관적으로 해결하기는 힘듬

• 따라서 완탐을 해야함

• 쪼갤 위치를 정해야한다.

  for (int i = 0; i < word.size() - 1; i++) // i가 word의 크기 -2 까지 접근
  	for (int j = i + 1; j < word.size(); j++) // j가 word 크기의 -1 까지 접근

  • mobitel 을 쪼갠다고 가정해보면,
  • 왼쪽 쪼갤 위치는 e 까지 가능하다.
  • 따라서, mobitel의 사이즈인 7 - 1 = 6 이므로 5까지 순회한다.
  • 오른쪽 쪼갤 위치는 l까지 가능하다.
  • 따라서 7 이므로 6까지 순회한다.
  • 정리하면, i는 0 ~ 5 j 는 i + 1 ~ 6 까지 순회하면서 어디소 쪼갤지 결정한다.

• 쪼갤 위치를 정햇으면, 쪼개보자

• STL string에 있는 substr을 사용한다.

• string substr (size_t pos = 0, size_t len = npos);

  • substr 은 index부터 len 길이만큼 자른다는 것에 유의하자.

• 코드

  #include <iostream>
  #include <string>
  #include <algorithm>
  #include <vector>
  
  using namespace std;
  
  string split_and_rev(string word, int a1, int a2)
  {
  	string str1, str2, str3;
  
  	str1 = word.substr(0, a1);
  	str2 = word.substr(a1, a2 - a1);
  	str3 = word.substr(a2, word.size() - a2);
  	//cout << str1 << ", " << str2 << ", " << str3 << endl;
  	reverse(str1.begin(), str1.end());
  	reverse(str2.begin(), str2.end());
  	reverse(str3.begin(), str3.end());
  	return (str1 + str2 + str3);
  }
  
  int main(void)
  {
  	string word;
  	string temp;
  	string cmp = "zzzzzzzzzzzzzzzzzzzzzzzzzz";
  
  	cin >> word;
  	for (int i = 1; i < word.size() - 1; i++)
  		for (int j = i + 1; j < word.size(); j++)
  		{
  			temp = split_and_rev(word, i, j);
  			if (temp < cmp)
  				cmp = temp;
  			//split_and_rev(word, i, j);
  		}
  
  	cout << cmp;
  }