[백준/C++] 1251번: 단어 나누기

문제

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

---

문제 요약

알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 진행한다.

 

1. 단어에서 임의의 두 부분을 골라 단어를 쪼갠다.

(각각은 적어도 길이가 1이상인 단어이다.)

 

2. 나누어진 세 개의 작은 단어들을 앞뒤로 뒤집고, 원래의 순서대로 합친다.

 

위 과정의 결과 문자열 중 사전 순으로 가장 앞서는 단어를 출력한다.

---

코드

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

using namespace std;

string str;

string first_str;
string second_str;
string third_str;

string res = "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz";

int main()
{
    cin >> str;

    for (int i = 0; i < str.size() - 2; i++) {
        for (int j = i + 1; j < str.size() - 1; j++) {

            first_str = str.substr(0, i + 1);
            second_str = str.substr(i + 1, j - i);
            third_str = str.substr(j + 1);

            reverse(first_str.begin(), first_str.end());
            reverse(second_str.begin(), second_str.end());
            reverse(third_str.begin(), third_str.end());

            res = min(first_str + second_str + third_str, res);

        }
    }

    cout << res;
    
    return 0;
}

---

코드 설명

1. 단어 str을 입력 받는다.

 

2. str을 세 부분으로 나누고 각각을 뒤집는다.

 

3. 세 부분을 다시 합쳐 결과 문자열을 구한다.

 

4. 위 과정을 이중 반복문을 통해 가능한 경우의 수를 모두 탐색한다.

(i와 j는 문자열을 세 부분으로 나눌 때, 각 부분의 경계 인덱스를 의미한다.)

---

고찰

1. substr

: string 클래스에서 문자열의 특정 부분을 추출하는 데 사용되는 멤버 함수

 

str 문자열의 0번 인덱스부터 길이 i + 1만큼의 부분 문자열을 추출하는 코드

first_str = str.substr(0, i + 1);

 

str 문자열의 j + 1번 인덱스부터 마지막 인덱스까지의 부분 문자열을 추출하는 코드

third_str = str.substr(j + 1);

 

2. reverse

: 문자열을 거꾸로 뒤집는데 사용되는 함수

 

first_str 문자열을 거꾸로 뒤집는 코드

reverse(first_str.begin(), first_str.end());

 

3. min을 통한 문자열의 사전 순 비교

=> algoritm 라이브러리의 min 함수를 통해 두 문자열의 아스키 코드를 비교하여 사전 순 비교를 할 수 있다.