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

문제

 

---

풀이

 

문제를 풀기 위해 문자열을 숫자화 했다. 간단하게 결과만 먼저 말하면, happy->01223 / new->123 / abab->0101로 숫자화 된다. 결과를 보면 알겠지만 그룹 단어라면 숫자화된 결과 값이 non-decreasing의 모습을 하고 있다. 이제 어떻게 이런 숫자가 나왔는지 설명하도록 하겠다.

 

각 알파벳을 숫자로 바꿀 flag 변수를 선언하고, 0으로 초기화 한다. 그리고 문자열을 처음부터 돌며 각 문자를 확인한다. 해당 문자가 등장한 적 없다면 현재의 flag 값으로 반영해주고 flag를 증가한다. 만약 읽었던 알파벳이라면 해당 알파벳에 어떤 flag값이 반영됐었는지에 대한 정보가 저장됐기 때문에 그냥 그걸 바로 가져오면 된다. 이렇게 문자열을 숫자로 바꿔서 non-decreasing 수열 여부를 확인한다.

---

소스코드

 

#include <iostream>
#include <cstring>
using namespace std;

bool isGroup(int* num, int length) {
	for (int i = 0; i < length-1; i++) {
		if (num[i + 1] < num[i])
			return false;
	}
	return true;
}

int main() {
	int N, count = 0, flag, length, i, j, num[100], checking[26];
	char word[101];

	cin >> N;
	for (i = 0; i < N; i++) {
		flag = 0;
		for (j = 0; j < 26; j++) //읽었던 알파벳인지 아닌지 체크하는 배열
			checking[j] = -1;
		cin >> word;
		length = strlen(word);
		for (j = 0; j < length; j++) {
			if (checking[word[j] - 97] == -1) { //처음 읽는 알파벳이면
				checking[word[j] - 97] = flag; //정보 입력
				num[j] = flag; //단어를 숫자로 변환하는 num 배열에 저장
				flag++;
			}
			else //이미 읽은 알파벳이면 미리 저장됐던 flag를 그대로 num 배열에 저장
				num[j] = checking[word[j] - 97];
		}
		if (isGroup(num, length)) //그룹 단어가 맞다면 num 배열이 증가하는 형태일 것 ex) happy = 01223
			count++;
	}
	cout << count << endl;
}