백준 1251번 문제 바로가기

bruteforce

간단한 길이 가장 쉬운 길이라고, 이래저래 고민해보았지만 결국 bruteforce가 가장 간단한 방법이었다. 문자열을 나누는 기준점을 i j 기준으로 하여 이중 for문을 돌려 새로운 문자열을 만들어낼 수 있다. 알파벳 순서로 앞서는지는 < comparison operator을 통해서 간단하게 확인할 수 있다.

다만 주의할 점은 reverse(begin, end) 함수는 begin ‘다음’ 위치부터 end ‘포함’ 위치까지 index을 뒤집는다. 즉, $ begin < index <= end $ 가 되는 셈! 따라서 이를 고려해서 index에 1을 더해주어 맞춰주어야 한다.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    string word, temp, ans="";
    string l1, l2, l3;
    
    cin >> word;
    for (int i=0; i<word.size(); i++){
        ans += 'z';
    }
    
    for (int i=0; i<word.size()-2; i++){
        for (int j=i+1; j<word.size()-1; j++){
            temp = word;
            reverse(temp.begin(), temp.begin()+i+1);
            reverse(temp.begin()+i+1, temp.begin()+j+1);
            reverse(temp.begin()+j+1, temp.end());
            if (ans > temp){
                ans = temp;
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

여담 - 틀린 풀이

처음 접근은 word의 각 자리를 ASCII로 바꾸어 vec에 저장한 뒤에, 최솟값 2개를 뽑아서 그것을 기준으로 reverse 시켰다. 얼핏 보기에는 큰 문제가 없어 보이지만, abbc 혹은 abbaabba와 같이 같은 알파벳이 여러 번 등장하는 경우, 최적의 답을 도출하지 못한다.

• 틀린 풀이니 주의!! ```cpp #include #include #include #include

using namespace std;

int main() { int prev=0, curr=0; string word; vector vec;

cin >> word;
for (char& c: word){
    vec.push_back(c-'0');
}

for (int i=0; i<2; i++){
    curr = min_element(vec.begin()+prev, vec.end()) - vec.begin() + 1;
    reverse(word.begin()+prev, word.begin()+curr);
    prev = curr;
}

reverse(word.begin()+prev, word.end());

cout << word;

return 0; }

```