(C++) - 백준(BOJ) 1251 : 단어 나누기

https://www.acmicpc.net/problem/1251

1251번: 단어 나누기

모든 단어를 검사하는 brute force로 푼 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

단어 word, 규칙대로 만든 단어를 저장할 map m, 나눈 부분의 index를 저장할 vector 변수 comb를 선언 후 word에 단어를 입력받습니다.

📔 풀이과정

 1. 단어의 길이는 최대 50이므로 그 중 나누는 구역은 3부분입니다. 50C2만에 나누는 index를 구할 수 있습니다.

 2. next_permutation함수를 사용해 뽑은 index를 기준으로 길이가 1이상이면서 뽑은 index가 0이 아니라면 규칙대로 나눈 각 단어들을 뒤집어 줍니다.

 3. 뒤집은 단어를 m에 넣어줍니다.

📔 정답출력

map변수는 삽입시 자동으로 오름차순 정렬되기 때문에 가장 첫 번째 원소를 출력하는 것이 사전순으로 가장 앞선 단어가 됩니다. 따라서 이를 출력해주면 정답입니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
string word;
map <string,int> m;
vector <int> comb;
int main(){
    cin >> word;
    comb.resize(word.size(), 1);
    for(int i = 0; i < 2; i++) comb[i] = 0;
    do{
        vector<int>idx;
        string newWord = word;
        for(int i = 0; i < comb.size(); i++) {
            if(!comb[i]) idx.push_back(i);
        }

        if(abs(idx[0] - idx[1]) < 1 || !idx[0]) continue;
        reverse(newWord.begin() , newWord.begin() + idx[0]);
        reverse(newWord.begin()+idx[0] , newWord.begin() + idx[1]);
        reverse(newWord.begin()+idx[1] , newWord.end());
        m[newWord] = 1;
    }while(next_permutation(comb.begin(), comb.end()));
    cout << m.begin()->first;
}