[BOJ][C] 1310번 그룹 단어 체커

안녕하세요.

오늘은 백준 1310번: 그룹 단어 체커(링크)  문제를 풀어보려고 합니다.

 

문제

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.

 

출력

첫째 줄에 그룹 단어의 개수를 출력한다.

 

예제 입력

3
happy
new
year

4
aba
abab
abcabc
a

5
ab
aa
aca
ba
bb

2
yzyzy
zyzyz

1
z

 

 

예제 출력

3

1

4

0

1

 

 

제한

시간 제한: 2초

메모리 제한: 128MB

 

---

풀이

단어가 연속되는지를 판별하는 것이 문제입니다.

 

우리는 일단 입력받은 단어가 그룹 단어라고 가정한 후, 만약 이후의 검사에서 그룹 단어가 아닌 걸로 판별되면 그룹 단어의 개수를 1 빼주도록 할 겁니다. 즉 아래와 같은 과정을 거칩니다.

 

1. 문자열을 입력받은 후, 그룹 단어의 개수 count를 1 증가시킵니다.
2. 맨 앞 인덱스부터 시작하여 해당 인덱스의 문자의 개수를 증가시키고 문자의 개수가 1개면 무시, 2개 이상이면 연속인지 검사합니다.
3. 만약 연속된 단어가 아니라면 count를 1 감소시킵니다.

 

그렇다면 가장 중요한 2개 이상일 때 연속된 단어인지는 어떻게 알 수 있을까요?

 

우리는 앞에서부터 문자의 개수를 증가시키면서 검사하고 있습니다.

 

 

만약 문자의 개수가 2라면, 현재 위치 이전에 같은 문자가 하나 더 있었다는 의미입니다.

연속된 단어일려면 문자의 개수가 2개가 될 때, 바로 뒷부분에 같은 문자가 있어야겠죠?

이는 문자의 개수가 3 이상일 때도 똑같이 적용됩니다.

 

 

따라서 문자의 개수 > 1 라면 str[j] != str[j-1]인지 검사합니다.

그 후 참이라면 count-- 하고 break합니다. 거짓이라면 아직까지는 그룹 단어이므로 따로 명령을 실행하지 않습니다.

 

 

예시로 알아보면 아래와 같습니다.

 

문제에서도 볼 수 있듯이, 문자가 하나만 있다면 연속된 것으로 판별합니다. count를 감소시키지 않습니다.

ex) abc, kin

 

문자가 2개 이상이라면, 뒤에 같은 문자가 있으면 연속된 것으로 판별합니다.

ex) abbc -> 세 번째 인덱스 검사 때, b가 2개 이상이고 뒤에 같은 문자 반복이므로 연속됨. count를 감소시키지 않습니다.

ex) babbc -> 세번째 인덱스 검사 때, b 바로 뒤가 a이므로 연속되지 않음. count를 감소시킵니다.

 

 

추가적으로, 단어의 개수만큼 반복해야 하므로 문자의 개수를 저장하는 배열을 계속 0으로 초기화해줘야 합니다.

 

정답

#include <stdio.h>
#include <string.h>
int main()
{
	int arr[26] = {0,}, n, count = 0;
	char str[102];
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%s",str);
		for(int i=0; i<26; i++){
			arr[i] = 0;
		}
		count++;
		for (int j = 0; j < strlen(str); j++)
		{
			arr[(int)str[j] - 97]++;
			if (arr[(int)str[j] - 97] > 1)
			{
				if (str[j] != str[j - 1])
				{
					count--;
					break;
				}
			}
		}
	}
	printf("%d", count);
	return 0;
}

 

 

 

---

이렇게 해서 백준 1310번 그룹 단어 체커 문제를 풀어보았습니다.

 

댓글로 질문을 남기시면 성실히 답해드리겠습니다

 

감사합니다!