[BOJ S4][C++] 백준 1544번: 사이클 단어

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

1544번: 사이클 단어

 

문제

사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다. 만약에 단어 A와 단어 B가 있을 때, 단어 B를 원형으로 써서, 단어 A와 같이 읽을 수 있으면, 두 단어는 같은 단어이다. 따라서, picture와 turepic은 같은 단어다.

N개의 단어가 주어졌을 때, 서로 다른 단어가 총 몇 개인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 단어가 한 줄에 하나씩 주어진다. 단어는 영어 소문자로만 이루어져 있다. N은 50보다 작거나 같은 자연수이며, 단어의 길이는 최대 50이다.

출력

첫째 줄에 서로 다른 단어가 몇 개인지 출력한다.

 

풀이

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

vector<string> v;

// s1 과 s2가 같은 사이클 단어인지 판별하는 함수
bool cycleWord(string s1, string s2) {
    for(int k=0; k<s1.size(); k++) {
        if(strcmp(s1.c_str(), s2.c_str()) == 0)
            return true;
        
        s1 += s1[0];
        s1.erase(0,1);
    }
    return false;
}

// 문자열 벡터 내에 i번째 문자열과 같은 사이클단어가 있는지 판별하는 함수
bool isThereSame(int i) {
    for(int j=i+1; j<v.size(); j++) {
        if(cycleWord(v[i], v[j]))
            return true;
    }
    return false;
}

// 서로 단어의 개수 카운트
int solution(int n) {
    int ans=0;
    
    for(int i=0; i<n; i++) {
        if(!isThereSame(i))
            ans++;
    }
    
    return ans;
}

int main() {
    int n;
    cin >> n;
    v.assign(n,"");
    for(int i=0; i<n; i++) {
        cin >> v[i];
    }
    
    cout << solution(n);
    
    return 0;
}

/*
 */