백준 2993 세부분

일단 문제 단계를 나눠봤다. 1) 세부분으로 나누기. 2) 나눈 부분 순서 바꾸고 합치기. 3) 작은지 계산하기.

1) 세부분으로 나누기

1이 2개 들어간 벡터(사이즈는 문자열보다 1개 작게) sort 한뒤 permutation으로 1 2개가 있는 위치를 나누는 위치로 지정하기로 했다. 

2) 나눈 부분 순서 바꾸고 합치기

합치는건 string + 를 이용하면 됐다. 나눈 부분 순서 바꾸는 걸 처음엔 vector를 생각했다. 그러다 그냥 반대로 바꾸면 된다는 걸 깨닫고 stack을 이용했다. stack 이용하면 나중에 들어온 걸 제일 처음 내보내므로 그대로 문자열에 합쳐주면 됐다. 

3) 작은지 계산하기

미리 temp string을 초기 값과 같게 설정해두고 min을 이용해서 사전순으로 작은지 안작은지 구했다.

 

코드>>

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
string str, temp;

int main() {
	
	cin >> str;
	int size_ = str.length();
	temp = str;
	vector<int> chooseChop;
	for (int i = 0; i < str.length()-1; i++) {
		if (i < 2) chooseChop.push_back(1);
		else chooseChop.push_back(0);
	}

	sort(chooseChop.begin(), chooseChop.end());

	do {
		int ch[3]; int temp_ch = 0;
		stack<char> before_[3];
		string temp_str = "";

		for (int i = 0; i <= chooseChop.size(); i++) {
			before_[temp_ch].push(str[i]);
			if (i == chooseChop.size()) break;
			if (chooseChop[i] == 1) {
				temp_ch++;
			}
		}
		for (int i = 0; i < 3; i++) {
			int size_stack = before_[i].size();
			for (int j = 0; j < size_stack; j++) {
				char ch = before_[i].top();
				temp_str += ch;
				before_[i].pop();
			}
		}

		temp = min(temp, temp_str);

	} while (next_permutation(chooseChop.begin(), chooseChop.end()));

	cout << temp;

	return 0;
}

자신감 회복하려고 실버5 단계 풀었는데 풀어서 마음이 좋다.. ^0^...

중간에 stack size를 미리 지정안하고 그냥 for문에 넣어서 stack값이 줄면서 for limit값도 줄어서 문자열이 잘렸었다. 오랜만에 하니 이런 거 챙기는 것도 쉽지 않다.

 

다른분이 푸신거 보니 reverse라고 문자열 반대로 해주는 함수가 이미 있었다 .. ! 역시 아는게 힘 ㅋㅋ

reverse(tmp.begin(), tmp.begin() + i+1);
reverse(tmp.begin()+i+1, tmp.begin() + j+1);
reverse(tmp.begin()+j+1, tmp.end());