[백준 1251] 단어 나누기

문제 풀이

 

주어진 문자열을 3개의 문자열로 나눈 다음에 각각의 문자열을 뒤집고, 뒤집은 3개의 문자열을 다시 합치면 된다.

문제는 어떻게 3등분을 하는가이다.

문제에서 문자열을 나눌 때 최소한 문자열의 길이가 1을 보장해야 한다고 명시되어있다.

 

문제에서 주어진 예시(arrested)를 3등분한다고 한다면? 아래처럼 다양하게 나올 것이다.

a / r / rested

a / rr / ested

a / rre / sted

...

arrest / e / d

 

하나의 색종이를 2등분으로 만들고 싶다면? 가위로 한 번 자르면 된다.

하나의 색종이를 3등분으로 만들고 싶다면? 가위로 두 번 자르면 된다.

우리는 3등분을 원하므로 총 2번의 경계선만 구하면 된다.

[문자열의 시작 지점 - i  - j - 문자열의 끝 지점]

i와 j는 3등분을 하는 경계선이라고 생각해보면 다음과 같이 정리할 수 있다.

(0 ~ i) 까지 부분 문자열 추출

(i ~ j) 까지 부분 문자열 추출

(i+j ~ 끝)까지 부분 문자열 추출

 

경계선을 구했다.

그런데 i를 어디까지 보면 될까?

문제에서 봤듯이 문자열은 최소 1개의 문자를 포함해야하므로 입력된 문자열 길이의 - 2까지만 돌면 된다.

그러면 j는 어디까지 보면 될까?

만약에 i가 최대 문자열의 길이 - 2 까지 오게 됬다면 j는 문자열의 길이 - i - 1까지만 돌면 된다.

 

다양한 문자열이 나타났을 때,

사전순으로 가장 앞선 단어를 구하기 위해서는 문자열끼리 비교해서 더 작은 문자열로 갱신하면 된다.

소스 코드

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    string str;
    cin >> str;
    
    string ans;
    int len = static_cast<int>(str.size());
    for(int i = 1; i <= len - 2; i++)
    {
        for(int j = 1; j <= len - i - 1; j++)
        {
            string a = str.substr(0,i);
            string b = str.substr(i,j);
            string c = str.substr(i+j);
            
            reverse(a.begin(), a.end());
            reverse(b.begin(), b.end());
            reverse(c.begin(), c.end());
            
            string ret = a + b + c;
            if(ans == "") ans = ret;
            else if(ans > ret) ans = ret;
        }
    }
    
    cout << ans << endl;
    return 0;
}