[백준]c++ 1251번 단어 나누기

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

1251번: 단어 나누기

1.문제 유형

문자열, 브르투포스(완전탐색)

 

단어의 길이가 최대 50이고 시간제한도 2초로 넉넉하기 때문에 완전탐색 방법(모든 경우를 다 확인)을 사용할 수 있다.

 

2.문제 파악

문자를 세부분으로 나누고, 각각 뒤집고,  합쳤을 때 사전순으로 가장 앞서는 단어를 출력하는 코드를 짜야한다.

주의할 점은 나눠진 부분의 길이가 1이상이어야한다. ex) ABCD를 ABC/D 이렇게 나누면 안된다.

문자열 함수를 사용해야할 부분은 나누기와 뒤집기

 

완전탐색으로 풀 것이기 때문에 문자를 나눌 범위를 지정하는게 중요했다.

 

3.문제 풀이

문자열 나누기(그림으로 이해)

: 두번째 단어의 시작 부분은 B~C까지

: 세번째 단어의 시작 부분은 두번째 단어 다음부터 D까지

 

 

문자열 뒤집기

: 뒤에서부터 앞으로 읽어들여 새로운 문자열 만들기

 

사전에서 가장 앞선 단어

: 그 단어를 저장해두었다가 단어를 새로 만들때마다 비교해서 갱신함

 

4. 코드

#include <iostream>
#include <string>
using namespace std;
string reverse(string s)
{
    string rev_result=""; 
    for(int i=s.length()-1;i>=0;i--)
    {
        rev_result+=s[i];
    }
    return rev_result;
}
 
int main()
{
    string input,fast_str="~"; //'~' == 아스키코드에서 가장 큰 값
    cin>>input;
    for(int i=1;i<input.length()-1;i++) 
    {
        string s_1,s_2,s_3,s;
        for(int j=i+1;j<input.length();j++)
        {
            s_1=reverse(input.substr(0,i));
            s_2=reverse(input.substr(i,j-i));
            s_3=reverse(input.substr(j));
            s=s_1+s_2+s_3;
            if(s<fast_str) //단어를 만들고 비교
                fast_str=s;
        }
    }
    cout<<fast_str;
    return 0;
}