[C] 백준 1316 : 그룹 단어 체커

 

 

1. 문제

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

1316번: 그룹 단어 체커

 

 

 

 

2. 접근

 

이 문제는 '그룹단어'의 개수를 찾아내는 문제인데, 이전에 나왔던 문자가 한 번 더 나오면 그룹단어에서 제외된다.

이 예시를 보면,

aba
abab
abcabc
a

a만 그룹 단어이다.

 

ab
aa
aca
ba
bb

 

위의 예시 또한 aca를 제외한 나머지가 그룹 단어이다.

 

                         i                                                 j 

0	1	2	...
a	a	b	...

a[i] = a[j] 일 때 key값을 생성하는데, a[i]와 a[j]가 같다는 것은 같은 단어임을 의미한다. (key값이 0인 경우)

이때 key값이 1보다 작은 경우에는 단어의 조건을 만족하기 때문에 1을 반환한다.

 

                      i                                                                            j 

0	1	2
a	b	a

그러나 1보다 크다면 a[j]와 a[j-1] 값을 비교해 j의 이전 단어도 같은지 확인한다. 같다면 1을 반환하고, 다르다면 0을 반환한다.

 

 

3. 정답

 

#include <stdio.h>
#include <string.h>
#define MAX 100

int Count(char a[], int len) {
	int key = 0;
	for (int i = 0; i < len; i++) {
		for (int j = i+1; j < len; j++) {
			if (a[i] == a[j]) {
				key = j - i;
				if (key > 1) // 연속되지 않은 경우
					if (a[j - 1] != a[j])
						return 0;
			}
		}
	}
	return 1;
}

int main() {
	char words[MAX];
	int n, cnt=0;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%s", words);
		cnt += Count(words, strlen(words));
	}
	printf("%d", cnt);
	
}