백준 2993(세 부분) c++

문제

2993번: 세 부분

주어진 단어를 세등분으로 나누어 한등분씩 역배치 하여 마지막에 역배치한 세등분을 다시 한등분으로 합쳐서

가장 단어의 사전순이 빠른 단어를 찾는 문제입니다.

처음에 세등분으로 나눈다는게 어떤 기준도 없고 해서 단순히 단어의 알파벳 개수의 12자 이면 4/4/4로 나누는 줄 알았습니다.

하지만 그러기에는 너무 단순했고 예제 문제도 틀리게 나왔습니다.

알고보니 세등분으로 나누는게 알파벳 개수의 제한 되지않고 알파벳 개수가 1개여도 나눌 수 있었습니다.

예를들어서 1/1/10 도 가능하고 10/1/1도 가능했습니다. 

따라서 나누는 부분을 for문으로 계속 바꿔주면서 그중에서 가장 사전순으로 먼저오는 단어를 갱신해주면 되는 

문제입니다.

---

string st;
cin >> st;
	
int size = st.size();
string z(size, 'z');

먼저 문자열 st를 입력받습니다. st는 우리가 세등분으로 나누어야할 단어입니다.

size라는 변수를 선언하고 size변수에 미리 입력받은 st의 길이를 초기화 해줍니다.

다음 z라는 문자열을 size만큼 알파벳 'z'로 초기화 해줍니다.

나중에 사전순으로 가장 앞에 오는 문자열을 할당받기 위해 min함수를 사용할건데 이때, z함수를 넣어주면

z함수는 'z'로만 이루어지기때문에 사전순이 가장 뒤에오기 때문에 min함수에 어떤 문자열이 와도 사전순이 앞인

문자열을 받을 수 있게 합니다.

예를들어 min(abcdefg , zzzzz) 하게 되면 자연스럽게 사전순이 앞인 abcdefg가 튀어나오게 됩니다.

for (int i = 0; i < size - 2; i++) {
		for (int j = i + 1; j < size - 1; j++) {
			string st2 = st;
			reverse(st2.begin(), st2.begin() + i + 1);
			reverse(st2.begin() + i + 1, st2.begin() + j + 1);
			reverse(st2.begin() + j + 1, st2.end());
			z = min(z, st2);
		}
	}
	cout << z;

이중 for문을 사용해 주었습니다. 

첫번째 for문에서 i는 0부터 시작해서 size-2까지 반복합니다. 이것이 첫등분으로 나눈것입니다.

두번째 for문에서 j는 i+1부터 size-1까지 반복합니다. 이것이 두번째 등분입니다.

문제에서 세등분으로 나누라고 했으므로 첫번째, 두번째 등분을 하면 자연스럽게 세등분으로 나누어지게 됩니다.

그다음 문자열 st2를 선언해주고 미리 앞에서 받은 st를 할당해 줍니다.

매번 사전순이 앞에오는 것을 갱신해주므로 st2는 for문이 계속 돌면서 초기화 해주는 역할을 합니다.

reverse(st2.begin(), st2.begin() + i + 1)는 첫등분의 단어를 역배치해줍니다. 

reverse(st2.begin() + i + 1, st2.begin() + j + 1)는 두번째 등분의 단어를 역배치 해줍니다.

reverse(st2.begin() + j + 1, st2.end())는 세번째 등분을 역배치 해줍니다.

이중 for문의 마지막 줄은 모든 문자가 'z'로 초기화된 z문자열을 min함수로 계속 갱신해줍니다.

마지막으로 이중 for문이 다 완료되면 z에는 사전순이 가장 앞에 있는 문자열이 들어가 있으므로

z를 출력해줍니다.

---

전체코드입니다.

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	string st;
	cin >> st;
	
	int size = st.size();
	string z(size, 'z');
	
	for (int i = 0; i < size - 2; i++) {
		for (int j = i + 1; j < size - 1; j++) {
			string st2 = st;
			reverse(st2.begin(), st2.begin() + i + 1);
			reverse(st2.begin() + i + 1, st2.begin() + j + 1);
			reverse(st2.begin() + j + 1, st2.end());
			z = min(z, st2);
		}
	}
	cout << z;

	return 0;
}