[ 백준 1251 ] 단어 나누기 (C++)

백준의 단어나누기(1251) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 주어진 문자열을, 3등분으로 나누어서 뒤집어서 다시 합쳤을 때, 사전순으로 가장 앞서는 단어를 출력해야 하는 문제이다.

   먼저 문자열을 어떻게 3등분으로 나눌지에 대해서 부터 알아보자.

   본인은 i , j 2개의 변수를 이용해서 나눠주었다.

   1. 0부터 i번째 문자까지

   2. i + 1번째부터, j번째 문자까지

   3. j + 1 ~ 마지막 문자까지

   이렇게 i, j 2개의 변수를 이용해서 나눠주었다. 이 때, 문자열은 반드시 3개가 나와야하고, 각 문자열은 최소 한개의 문자를

   포함해야 한다.

   "ABCDEF" 라는 문자가 있다면, i가 아무리 커도, 'D'보다 더 넘어가버리면 안된다.

   i가 'D' 초과일 경우, 즉, i가 E를 가리키고 있다고 가정해보자.

   1번문자열은 A ~ E , 2번문자열은 F, 3번문자열은 ??? 존재하지 않기 때문이다. 따라서, i의 값이 아무리 커봤자,

   문자열의 길이 - 1 보다는 작은 범위에서 계산을 해줘야 한다. j의 값도 마찬가지이다. j의 값이 마지막 문자열을 가리켜 버리면,

   3번조건인 j + 1 ~ 마지막 문자에서 오류가 발생할 수 있기 때문이다.

  

   

2) 문자열은 나누는 것은, 위에서 말한 방식 그대로 나누었다. 임의의 문자열 3개를 만들어서,

   0번째부터 i번째까지, i+1 ~ j번까지, j + 1 ~ 마지막 까지 3개로 나누어서 뒤집은 다음 합쳐주었다.

   이후 ,순서를 비교해서 더 빠른 문자열이 있다면 갱신시켜주는 방식으로 구현해주었다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<algorithm>
 
#define endl "\n"
using namespace std;
 
string Inp, Answer;
int Len;
 
void Input()
{
    cin >> Inp;
    Len = Inp.length();
}
 
void Divide(string S, int First, int Second)
{
    string A, B, C;
    A = B = C = "";
    
    for (int i = 0; i <= First; i++) A = A + S[i];
    for (int i = First + 1; i <= Second; i++) B = B + S[i];
    for (int i = Second + 1; i < Len; i++) C = C + S[i];
 
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());
    reverse(C.begin(), C.end());
 
    string Temp_Answer = A + B + C;
    
    if (Answer == "") Answer = Temp_Answer;
    else
    {
        if (Answer > Temp_Answer) Answer = Temp_Answer;
    }
}
 
void Solution()
{
    //i j를 돌리는데, 0~i번까지 i + 1번부터 j번까지, j + 1 ~ Len번까지
    for (int i = 0; i < Len-1; i++)
    {
        for (int j = i; j < Len-1; j++)
        {
            if (i >= j) continue;
            string Temp = Inp;
            Divide(Temp, i, j);
        }
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}