백준 11875번 MULTIGRAM

문제 링크입니다: https://www.acmicpc.net/problem/11875

문제에서 요구하는 바는 문자열을 문자열의 부분 문자열의 조합으로 만들 수 있을 때, 길이가 제일 작은 부분 문자열을 구하는 문제였습니다.

예를 들어, bbabab가 주어졌을 때, 부분 문자열 bba를 적절히 순서를 바꾸면 bab가 되므로 요구하는 답은 bba입니다.

알고리즘은 아래와 같습니다.

1. 문자열이 부분 문자열의 조합으로 이루어져있어야하기 때문에 부분 문자열의 길이가 문자열의 길이로 나누어 떨어져야합니다.

2. 해당 부분 문자열로 다른 부분 문자열을 만들 수 있는지 없는지를 판별하기 위해 알파벳 오름차순 정렬을 하여 같으면 가능하고 다르면 불가능하다고 판별합니다.

3. 최초로 조건을 만족하는 부분 문자열을 출력하고, 만약 모든 부분 문자열에 대해 성립하지 않는다면 -1을 출력합니다.

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        string s;

        cin >> s;

       

        bool result = false;

        for(int i=1; i<s.length(); i++)

                 //나누어 떨어져야 적절히 나눌 수 있다

                 if (s.length() % i == 0)

                 {

                         string a = s.substr(0, i);

                         sort(a.begin(), a.end());

 

                         bool multigram = true;

                         for (int j = i; j < s.length(); j += i)

                         {

                                 string b = s.substr(j, i);

                                 sort(b.begin(), b.end());

                                

                                 //하나라도 anagram이 아닐 경우

                                 if (a != b)

                                 {

                                          multigram = false;

                                          break;

                                 }

                         }

 

                         if (multigram)

                         {

                                 cout << s.substr(0, i) << "\n";

                                 result = true;

                                 break;

                         }

                 }

 

        if (!result)

                 cout << -1 << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~