Boj 1464) 뒤집기 3

문제

백준 1464

설명

연속해서 두번 뒤집어보자.

   1 2 3 4 5  
=> 4 3 2 1 5   // n=4 reverse  
=> 5 1 2 3 4   // n=5 reverse

그러면 5 가 기존 문자열에 앞에 오는 것과 같은 효과를 갖게 된다. 다시말해 우리는 두가지 연산을 할 수 있다.

• 기존 문자열의 앞에 문자를 추가하기
• 기존 문자열의 뒤에 문자를 추가하기
• 사실 길이 2 만큼의 기회가 있다면 모든 경우의 수는 네가지이지만 위 경우에서 뒤집혀있냐 아니냐의 차이기 때문에 큰 의미는 없다.

이를 깨달으면 문제가 간단해진다. 사전순으로 가장빠른 문자열을 만들기 위해서는 기존 문자열의 맨 앞문자보다 사전순으로 같거나 빠르면 문자열의 앞에 넣으면 된다.

시간 복잡도

O(\(\mathrm{N}\))

일일히 뒤집는 연산을 수행한다면 뒤집는 연산을 고려해야하므로 시간복잡도가 O(\(\mathrm{N}^2\)) 가 된다. 하지만 문자를 단순히 추가만한다면 선형시간에 해결할 수 있다.

코드

int main()
{
	string in, ans; 
	cin >> in; ans = in[0];
	for (int i = 1; i < in.length(); i++)
		ans = in[i] <= ans[0] ? in[i] + ans : ans + in[i];
	cout << ans;
}