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

문제링크

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

1544번: 사이클 단어

문제

  사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다.

  만약에 단어 A와 단어 B가 있을 때, 단어 B를 원형으로 써서, 단어 A와 같이 읽을 수 있으면, 두 단어는 같은 단어이다.

  따라서, picture와 turepic은 같은 단어다.

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

입력

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

출력

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

 

풀이

원형으로 돌려서 확인했을 때 다른 단어를 담아줄 벡터를 이용한다.

문자열을 입력 받으며 벡터에 있는 각 단어마다 아래의 절차를 거쳐 확인한다.

1. 입력 받은 단어가 벡터에 있는 단어와 일치하는가

2. 일치한다면 벡터에 추가하지 않고 빠져나온다.

3. 일치하지 않는다면 단어의 첫 알파벳을 뒤로 넘겨주고 다시 1과 2를 반복한다.

4. 단어의 길이만큼 뒤로 넘기면서 확인해도 같지 않다면 벡터에 추가한다.

코드

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n;
    string word;
    vector<string> v;    // 다른 단어를 담아줄 벡터
    cin >> n;
 
    for (int a = 0; a < n; a++) {
 
        cin >> word;
 
        if (v.empty()) {
            v.push_back(word);
        }
 
        bool same = false;
        for (int i = 0; i < v.size(); i++) {
            for (int j = 0; j < v[i].size(); j++) {
                // 같은 단어가 있다면 search 종료
                if (word == v[i]) {
                    same = true;
                    break;
                }
                // 단어가 같지 않다면 맨 앞글자를 맨뒤로 보내줘서 다시 확인
                else {
                    v[i] = v[i] + v[i].at(0);
                    v[i].erase(v[i].begin());
                }
            }
        }
        // 다르다면 벡터에 추가
        if (same == false) {
            v.push_back(word);
        }
    }
    cout << v.size();
 
}

 

Memo