[BOJ] 1464 번 - 뒤집기 3

백준 1464번 - 뒤집기 3

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	388	104	78	33.051%

문제

세준이는 어떤 문자열 S를 뒤집으려고 한다. 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자. i만큼을 뒤집는다는 소리는 그 문자열의 처음부터 정확하게 i개의 문자를 역순으로 뒤집는 것이다. 세준이는 1부터 N까지 수를 차례대로 생각한다. 그리고, 뒤집을지 안 뒤집을지 선택할 수 있다.

예를 들어, S="BCDAF" 이고, 세준이가 길이 1만큼을 뒤집지 않고, 길이 2만큼도 뒤집지 않고 세준이가 길이 3만큼을 뒤집는다고 하면 문자열은 DCBAF가 된다. 다시 여기서 4만큼 뒤집으면 ABCDF가 된다. 그리고, 마지막으로 길이를 5만큼 뒤집지 않으면 주어진 문자열 S를 사전순으로 가장 앞서게 만들 수 있다.

문자열 S가 주어졌을 때, 위와같은 뒤집기 방법으로 만들 수 있는 문자열 중 사전순으로 제일 앞서는 것을 출력하시오.

입력

첫째 줄에 문자열 S가 주어진다. 문자열의 길이는 최대 10,000이다. 알파벳 대문자만 들어온다.

출력

첫째 줄에 사전순으로 가장 앞서는 정답을 출력한다.

---

예제 입력 1

BCDAF

예제 출력 1

ABCDF

출처

www.acmicpc.net/problem/1464

1464번: 뒤집기 3

알고리즘 분류

• 그리디 알고리즘
• 문자열

접근 방법

처음 접근 할 때, 도저히 규칙을 못 찾겠어서 완전 탐색으로 문자열을 만들어 가능한 문자열의 조합을 모두 출력해보았다.

 

문자열을 reverse하는 것은 문자열의 0번째 인덱스 부터 i번째 인덱스까지 reverse하는 것이므로, 사전 순으로 앞서 있는 문자를 만날 경우 영향을 덜 받는 뒤쪽 인덱스 쪽으로 밀어 넣고 마지막에 reverse를 시키면 되지 않을까? 라는 생각이 들었다.

[ 무조건 0번째 문자부터 뒤집다는 조건이 있으므로, 사전순으로 작은 문자를 뒤쪽으로 보내자는 생각 ]

 

i번째 문자를 i+1번째 문자로 보내는 방법은 한 가지 방법만 존재한다.

i번째 문자까지 뒤집고 다시 i+1번째 문자까지 뒤집는 것이다.

 

0.     ${a_1 a_2 a_3 a_4 ... a_k a_{k+1}}$  // 초기상태

1.     ${a_k a_{k-1} ... a_4 a_3 a_2 a_1 a_{k+1}}$ // i번째 문자까지 뒤집기

2.     ${a_{k+1} a_1 a_2 a_3 a_4 ... a_{k-1} a_k}$ // i+1번째 문자까지 뒤집기

 

단, ${a_k < a_{k+1}}$ 일 경우에만 다음과 같은 작업을 반복해야한다. 우리의 목적은 일단 사전순으로 앞서 있는 문자를 뒤로 보내는 것이 목적이기 때문이다.

 

1부터 N까지의 수를 차례대로 생각했을 때, k번째 Stage에서 ${a_k < a_{k+1}}$ 일 경우 k번째 있는 문자를 k+1에 있는 문자로 옮기게 되는데 마지막에는 결국 사전순으로 가장 작은 수가 맨 뒤에 오게 된다.

이 후, 위 값을 reverse해준다면 우리가 원하는 사전순으로 가장 앞서는 정답을 구할 수 있게 된다.

 

reverse stl이 N의 시간복잡도를 가지므로 위 과정을 구현한 소스 코드1 은  ${O(N^2)}$ 에 구할 수 있다. 

---

소스 코드1을 복기하다가 규칙을 보았다!

결국 ${a_k < a_{k+1}}$ 라면 위의 로직의 2번 과정까지 거쳤을 때

${a_{k+1} a_1 a_2 a_3 a_4 ... a_{k-1} a_k}$ 가 나오지 않는가? 

 

${a_k \geq a_{k+1}}$ 라면 어떻게 될까?

${a_1 a_2 a_3 a_4 ... a_{k-1} a_k a_{k+1}}$ 가 나오게 된다!

 

현재까지 구한 문자열이 s라고 하고 현재 문자가 k라고 하였을 때, ${s_{k-1} < a_k}$ 일 경우는 ${a_k + s}$

${s_{k-1} \geq a_k}$ 일 경우는 ${s + a_k}$ 로 치환해주면  reverse 함수를 호출 할 필요없이 동일하게 구현이 가능하다.

 

모든 Stage를 마치고 정답을 출력할 때는 s의 reverse를 출력하면 된다.

 

다음 로직은 소스코드2에 구현하였다.

시간 복잡도는 ${O(N)}$이다.

 

 

소스 코드1

#include <bits/stdc++.h>
using namespace std;
string str;
//set<string> answers;
//void select(string str, int cnt){
//	if( cnt == str.size() ){
//		answers.insert(str);
//		return ;
//	}
//	// 뒤집는다.
//	string rev = str;
//	reverse(rev.begin(), rev.begin() + cnt + 1) ;
//	select( rev, cnt + 1 );
//	// 뒤집지 않는다.
//	select( str, cnt + 1 );
//
//}
int main(void){


    // what is best solution ?
    // 일단 사전순으로 가장 작은 것이 뒤쪽으로 가도록 맞춘다.
    // 왜?? 뒤쪽이면 안건들여도 되거든?
    // 마지막에 뒤집기만 하면 되잖아

//	while(true){
//		cout << "input : ";
//		cin >> str;
//		answers.clear();
//
//		select(str, 0);
//		cout << " \t === 출력시작=== \t " << '\n';
//		for( set<string>::iterator it = answers.begin(); it != answers.end(); it++ ){
//			cout << *it << '\n';
//		}
//		cout << "\n-----------------------\n";
//	}

    cin >> str;

    for(int i=0; i<str.size()-1; i++){
        // 사전순으로 앞에 오는 것을 뒤로 보내서 다시 reverse 시킨다.
        if( str[i] < str[i+1] ){
            // 1...i까지 reverse 이 후 1 ... i+1 까지 다시 reverse
            reverse(str.begin(), str.begin() + i + 1);
            reverse(str.begin(), str.begin() + i + 2);
        }
    }
    reverse(str.begin(), str.end()) ;
    cout << str;

    return 0;
}

소스 코드2

#include <bits/stdc++.h>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    string str;
    cin >> str;

    string s = str.substr(0,1);
    for(int i=1; i<str.size(); i++){
        if( s[i-1] < str[i] ){
            s = str[i] + s;
        }else{
            s = s + str[i];
        }
    }
    reverse(s.begin(), s.end());
    cout << s;
    return 0;
}