문제

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

---

풀이

시간 초과

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

bool isGroupWord(string s) {
	for(int i = 0; i < s.size() - 2; i++){
		for(int j = i + 2; j < s.size(); j++){ 
			if(s[i] == s[j] && s[j] != s[j - 1]) 
				return false; 
		}
	}
	return true; 
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; 
	cin >> n; 

	int cnt = 0; 
	while(n--){ // 최대 100 
		string s; 
		cin >> s; 
		if(isGroupWord(s)) cnt++; // 최대 100^2 
	}

	cout << cnt; 
	
	return 0; 
}

O(n^3)의 시간복잡도로는 시간초과가 발생한다. (최대 1,000,000번의 연산)

다른 풀이

https://beginnerdeveloper-lit.tistory.com/104

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; 
	cin >> n; 
	
	int cnt = n; 
	while(n--){
		string s; 
		cin >> s; 

		bool appeared[26] {false}; 

		// 첫번째 알파벳 문자에 대한 출현 유무 처리 
		int index = s[0] - 'a'; 
		appeared[index] = true; 

		for(int i = 1; i < s.size(); i++){ 
			int index = s[i] - 'a'; 
			
			// 이전 문자와 같지 않은데, 전에 나왔던 문자인 경우 
			if(s[i] != s[i - 1] && appeared[index]){
				cnt--; // 그룹 단어 X 
				break; // 다음 케이스로 이동 
			}

			if(!appeared[index]){ 
				appeared[index] = true; 
			}
		}
	}

	cout << cnt; 
	
	return 0; 
}

이중 for문으로 동일한 문자가 다시 등장하는지 검사하는 게 아니라, 알파벳의 출현 유무 자체를 배열에 저장하여 그룹 단어를 판별하는 방식이다. 시간 복잡도는 O(n^2)으로 줄어들었다.