문제
그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.
단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.
풀이
find() 함수의 유뮤로 차이나는 두 가지 방식으로 풀었다.
방법 1) find() 함수 안쓰고
방법 2) find() 함수 쓰고
문제를 풀기 위한 접근 방식은 간단하다.
📌 이 문제의 중요한 포인트는 문자가 이어지는 경우를 제외하고 문자가 중복되는 경우 를 찾아야 한다는 것이다.
따라서, 차근히 정리해보면
- 동일한 문자가 이어지지 않는 부분에서
- 이어지지 않는 곳의 앞문자가 단어에서 그 뒤쪽의 문자들 중에 존재하는지 알아보면 된다. (존재하면 해당 단어는 그룹 단어가 아니다.)
(뒤쪽의 문자 : 앞문자의 위치+2 ~ 단어 끝까지)
예를 들어 설명하면,
a(ab)ba에서 문자가 이어지지 않는 부분은 -> (ab)의 부분
이어지지 않는 곳의 앞문자 : a
단어의 앞문자의 위치 = a의 위치 : 인덱스 1
따라서 인덱스 1보다 뒤쪽의 문자 : bba 부분에서 a가 존재하는지 판단 => a 존재하므로 그룹 단어X
여기서, 어차피 문자가 이어지지 않음을 아니까 인덱스 2부터인 bba가 아니라 인덱스 3부터인 ba만 검사하도록 할 것이다.
즉, 단어의 앞문자의 위치+2 부터 시작하는 뒤쪽의 문자들 중에서 존재여부를 파악할 것임.
풀이 코드
방법 1. find() 함수 사용 X
#include<iostream>
using namespace std;
//방법 1. find() 함수 사용 안함
int main(void)
{
cin.tie(NULL); ios_base::sync_with_stdio(false);
int n, cnt=0; //여기서 cnt는 그룹 단어가 아닌 것들의 개수!
cin>>n;
string str;
for(int i=0;i<n;i++){
cin>>str;
bool check=false;
if(str.size()>=3){
for(int j=0;j<str.size()-2;j++){
for(int k=j+2;k<str.size();k++){
if(str[j]!=str[j+1]&&str[j]==str[k]){
check=true;
break;
}
}
}
if(check) cnt++;
}
}
cout<<n-cnt;
}방법 2. find() 함수 사용 O
#include<iostream>
using namespace std;
// 방법2. find()함수 사용
int main(void)
{
cin.tie(NULL); ios_base::sync_with_stdio(false);
int n,cnt=0; //여기서 cnt는 그룹 단어가 아닌 것들의 개수!
cin>>n;
string str;
for(int i=0;i<n;i++){
cin>>str;
if(str.size()>=3){
for(int j=0;j<str.size()-2;j++){
if(str[j]!=str[j+1]){ //문장에서 앞문자와 뒷문자가 다른 위치에서
if(str.find(str[j],j+2)!=std::string::npos){ //앞문자가 문장 내에 또 있다면
cnt++;
break;
}
}
}
}
}
cout<<n-cnt;
}방법 2. 코드 설명
if(str.size()>=3){단어의 문자 개수가 1개나 2개인 경우는 무조건 그룹 단어이므로 검사에서 제외한다.
for(int j=0;j<str.size()-2;j++){
if(str[j]!=str[j+1]){ //문장에서 앞문자와 뒷문자가 다른 위치에서
if(str.find(str[j],j+2)!=std::string::npos){ //앞문자가 단어 내에 또 있다면
cnt++;
break;
}
}
}for(int j=0;j<str.size()-2;j++) 단어의 맨 뒤 두 문자는 검사하지 않아도 된다. 맨 뒤 두 문자가 다르던, 같던 그룹 단어 판단에 영향을 주지 않는다. 따라서 j<str.size()-2 로 하였다.
if(str[j]!=str[j+1]) 앞 문자와 뒷 문자가 다른 위치 = 동일한 문자가 이어지지 않는 부분이라면, 그 부분의 앞문자에 해당하는 인덱스 번호를 가지고 이제 해당 앞문자와 같은 문자가 뒷부분에 있는지 검사한다.
if(str.find(str[j],j+2)!=std::string::npos) find() 함수를 통해 단어 내 문자를 찾는다. str[j] = 앞문자 와 같은 문자가 j+2 앞문자의 인덱스보다 두 번째 뒤의 문자들 중에 있는지 찾는다.
🙄 find() 함수란? 내 문자열.find(찾을 문자열, 시작위치) 🙄
단어 내에서 중복하는 문자를 찾은 경우, cnt++ 를 늘린다. cnt는 그룹 단어가 아닌 것의 개수 이다.
따라서, 마지막에 n-cnt 를 출력하면 총 단어의 개수 중 그룹 단어가 몇 개 인지 알 수 있다.
