PS/BOJ
백준 1544번: 사이클 단어 (C++)
도비(Doby)
2023. 3. 1. 10:39
https://www.acmicpc.net/problem/1544
1544번: 사이클 단어
사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다. 만약에
www.acmicpc.net
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;
}