백준 1544번: 사이클 단어 (C++)

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

1544번: 사이클 단어

---

Level: Silver IV

Solved By: Brute-Force, String

 

N의 최고 범위가 50, 문자열의 최대 길이가 50이라서 Brute-Force를 해도 되겠다는 생각이었습니다.

Brute-Force를 통해 비교를 할 때, 사이클 단어인지 판정하기 위해 string 헤더 파일의 substr 메서드를 활용했습니다.

두 단어가 사이클 단어라면, 비교한 단어 b를 a로 바꾸어 vector에 a를 할당하였습니다.

그리고, Coordinate Compression의 테크닉인 erase와 unique를 활용하여 중복된 값들을 전부 없애고, vector의 사이즈로 최종적인 답을 도출했습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int N;
vector<string> v;

bool check(string a, string b){
    if(a.length() != b.length()) return false;
    
    for(int i = 0; i < b.length(); i++){
        string temp = b.substr(i, b.length() - i) + b.substr(0, i);
        if(a == temp) return true;
    }
    
    return false;
}

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        string s; cin >> s; v.push_back(s);
    }
    
    for(int i = 0; i < v.size(); i++){
        for(int j = i + 1; j < v.size(); j++){
            if(i == j) continue;
            // 같다면, 앞의 것과 똑같이 바꿀 것
            if(check(v[i], v[j])){
                v[j] = v[i];
            }
        }
    }
    
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    
    cout << v.size();
    
    return 0;
}