import sys N = int(input()) #테스트 케이스 개수 입력 res = N #결과값 (그룹 단어가아니면 1개씩 뺄거기 때문에 처음 결과는 단어 입력 개수) for _ in range(N): s = sys.stdin.readline() #단어 입력 cnt = 0 #연속된 문자 개수 for i in range(len(s)-1): cnt += 1 #연속된 문자면 계속 센다. if s[i] != s[i+1]: #연속된 문자가 아닐 경우 if cnt != s.count(s[i]): #지금까지 센 문자와 단어 안에서의 전체 그 문자의 개수가 다르면 res -= 1 #정답이 아니므로 1빼줌 break #그룹 단어가 아닌게 확인 되었으니 그 단어를 놓아주고 다음 단어 입력받으러 간다. cnt = 0 #연속된 문자가 아니었으므로 개수를 다시 0으로 초기화 print(res) #결과 출력
살짝 까다로운 문제였다.
접근법은 먼저 처음 나왔던 문자가 연속되지 않은 문자 뒤에 오는가를 체크하면 된다.
word | a | a | b | b | b | c | c | d | d | e | c |
---|---|---|---|---|---|---|---|---|---|---|---|
✔ | ✔ |
a의 연속된 개수는 2개이다. 그리고 단어에서 전체 a의 개수는 2개이다.
따라서 아직까지는 그룹 단어라고 할 수 있다. 그 다음 b를 보자.
word | a | a | b | b | b | c | c | d | d | e | c |
---|---|---|---|---|---|---|---|---|---|---|---|
✔ | ✔ | ✔ |
b의 연속된 개수는 3개이고 전체 개수도 3개이다.
word | a | a | b | b | b | c | c | d | d | e | c |
---|---|---|---|---|---|---|---|---|---|---|---|
✔ | ✔ | ✔ |
c의 연속된 개수는 2개인데, 전체 개수는 3개이다. 여기서 이 단어는 그룹 단어가 아님을 알 수 있다.
이런 방식의 알고리즘을 구현하면 된다.
#include <string> #include <iostream> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; int answer = 0; while (N--) { string S; cin >> S; bool check = true; if (S.size() <= 2) answer++; else { for (int i = 0; i < S.size() - 2; i++) { for (int j = i + 2; j < S.size(); j++) { if (S[i]!=S[i+1] && S[i] == S[j]) check = false; } } } if (S.size()>2 && check==true) answer++; } cout << answer; }