[C++] 그룹 단어 체커 : 1316번

문제

 

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

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

---

문제 해석

 

그룹단어가 되기 위한 조건은

이전에 나왔던 알파벳이 연속이 끊긴 상태에서 재등장하면 안된다.

또한, abc 처럼 각 알파벳이 한 번만 나와도 '1'번의 연속으로 본다. 즉, abc 는 그룹단어이다.

bbaacc 는 그룹단어이지만, bbaacca 는 그룹단어가 아니다. a 의 연속이 끊긴 상태에서 a 가 다시 등장했기 때문.

 

따라서, 그룹단어가 아닌 조건은

현재 알파벳이 이전 알파벳과 같은 알파벳이 아니면서,

현재 알파벳이 이전에 나온적이 있는 알파벳이라면 그룹단어가 아니다.

---

풀이

#include <iostream>
using namespace std;

bool isGroupWord(string word);

int main()
{
	int testCase; // 테스트 케이스
	int count = 0; // 갯수 세기
	cin >> testCase; cin.ignore(); // 테스트 케이스 수 입력
	string word; // 문자열 생성
	for (int i = 0; i < testCase; i++)
	{
		cin >> word;
		cin.ignore();
		if (isGroupWord(word)) // 그룹단어 인지 확인
		{
			count++; // 맞다면 갯수 세기
		}
	}
	cout << count;
}
bool isGroupWord(string word)
{
	bool isExist[26] = { 0, }; // 0번부터 A 알파벳 배열, 알파벳이 등장하면 true
	bool groupWord = false; // 그룹단어인지?
	for (int j = 0; j < word.length(); j++) // 문자마다 검사
	{
		if (j == 0) // 첫 번째 일 경우는 존재하는지 체크만 하고 넘어감
		{
			isExist[word[j] - 'a'] = true;
			groupWord = true;
		}
		// 전 글자와 같지 않고, 전에 존재했던 알파벳이 아니라면
		else if (word[j] != word[j - 1] && isExist[word[j] - 'a'] == false)
		{
			isExist[word[j] - 'a'] = true; // 해당 알파벳 존재여부 표시
			groupWord = true; // 그룹단어가 맞음
		}
		// 전 글자와 같지 않고, 이전에 존재했던 알파벳이라면
		else if (word[j] != word[j - 1] && isExist[word[j] - 'a'] == true)
		{
			return false; // 알파벳의 연속이 끊긴 것이므로 그룹단어가 아니므로 바로 종료
		}
	}
	return groupWord; // 최종적으로 groupWord의 값 리턴
}

 

1. 우선 단어를 입력받는다.

2. isExist 라는 bool 배열을 26개만큼 만든다. >> 알파벳이 26개 이기 때문

3. isExist 배열은 0~25번의 인덱스를 사용한다. 각 인덱스는 0번은 a, 1번은 b, 2번은 c....25번은 z 를 의미한다.

4. 단어의 문자를 하나씩 검사하며 현재 알파벳이 존재한다고 isExist의 위치에 기록한다.

isExist[word[j] - 'a'];

만약 word[j] 가 알파벳 'c' 라면, c 에서 a 를 뺀 값은 아스키 코드에서 99 - 97 과 같으므로 2의 값을 가진다.

따라서, isExist[2] 와 같고 이것은 c 의 자리의 isExist 를 true로 바꾸는 것과 같다. (isExist[0] 은 'a' 를 의미, [1] 은 'b' 를 의미)

 

5. 검사를 진행하다가 연속적인 글자가 아닌데, isExist 의 값이 true 라면 이전에 등장했던 알파벳이므로

그룹단어가 아니게 된다. 이외의 경우는 그룹단어로 판단한다.

// 전 글자와 같지 않고, 이전에 존재했던 알파벳이라면
		else if (word[j] != word[j - 1] && isExist[word[j] - 'a'] == true)
		{
			return false; // 알파벳의 연속이 끊긴 것이므로 그룹단어가 아니므로 바로 종료
		}

6. 그룹단어의 갯수를 세서 출력한다.