[1544번] 사이클 단어

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Map STL

맵을 이용하여 문제를 풀어보자.

우선 이 문제의 핵심은 product가 있다면 productproduct로 스트링을 만들어 줘야한다.

왜냐면 그다음 문자열이 tproduc라면 productproduct에 걸리기 때문이다.

따라서 이 문제를 풀 때 맵을 2개를 만들되, 하나는 product가 있는 original인 맵을, 하나는 productproduct가 들어있는 맵을 만든다.

그리고 pair를 이용하여 값을 더 주는데 first에는 인덱스 번호를, second에는 productproduct의 원본 크기를 넣어준다.(여기선 7)

이제 for문을 보자.

첫번째 for문은 productproduct같은 연속된 문자열을 넣어둔 맵이고, 두번째 for문은 product같은 original 문자열이 있는 맵이다.

첫번째 if문에서 < 문자열 A,B의 인덱스가 다르면(복사된 문자열과 원래 문자열이 같은게 아니라면) > 이 나타난다.

즉, product와 productproduct는 당연히 검사에서 제외되어야 하니 인덱스가 다른 것들끼리 본다.

두번째 if문은 원래 문자열 길이 자체가 같다고 되어있는데 

예를들어 인풋이

2

a

aa라면

저 조건이 없으면 답은 1이 나오지만 실제로는 a와 aa는 엄연히 다르다. 따라서 답은 2가 나와야 하기에 저 코드가 있는 것이다.

즉, 초기 길이부터 같아야 같은 단어인지 파악하는 전제가 된다.

if, else if, else는 인덱스가 어떻게 구성되어있는지, 갱신을 해주는 방식이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
 
using namespace std;
 
typedef pair<int, int> pii;
 
map<string, pii> mp;
map<string, pii> ori;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        string str;
        cin >> str;
 
        ori[str].first =  i;
        ori[str].second = str.size();
        int tmp = str.size();
 
        str += str;
        mp[str].first = i;        
        mp[str].second = tmp;
    }
 
    int cnt = -1;
    bool chk = false;
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        for (auto it2 = ori.begin(); it2 != ori.end(); it2++)
        {
            // 문자열 A,B의 인덱스가 다르면(복사된 문자열과 원래 문자열이 같은게 아니라면)
            if (it->second.first != it2->second.first)
            {
                // 이때 서로 원래 문자열 길이 자체가 같고, 원래 문자열이 복사된 문자열내에 존재할 경우
                if (it->second.second == it2->second.second && it->first.find(it2->first) != string::npos)
                {
                    // 이미 값이 존재하면 그 값을 대입, 그게 아니면 신규값 대입
                    if (it->second.first <= -1)
                        it2->second.first = it->second.first;
                    else if (it2->second.first <= -1)
                        it->second.first = it2->second.first;
                    else
                    {
                        it->second.first = cnt;
                        it2->second.first = cnt; 
                    }
 
                    chk = true;
                }
            }
        }
 
        // cnt가 이용된 경우에만 cnt--
        if (chk)
        {
            cnt--;
            chk = false;
        }
    }
 
    // 같은 인덱스 -> 중복되는 문자열들
    map<int, int> ans;
    for (auto it = ori.begin(); it != ori.end(); it++)
        ans[it->second.first]++;
 
     cout << ans.size();
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>