[C / C++] 백준 1316번 - 그룹 단어 체커

백준 1316번 : https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

---

✅ 문제 설명

그룹단어란 단어에 존재하는 모든 문자에 대해서 각 문자가 연속해서 나타는 경우만을 말한다.

ccazzzzbb는 c,a,z,b가 모두 연속적으로 나타나며,

kin도 하나씩이지만 k,i,n이 모두 연속해서 나왔기 때문에 그룹단어로 볼 수 있다.

 

그러나 aaccbbc는 c가 떨어져서 나타났기 때문에 그룹단어가 아니다.

---

✅ 알고리즘 설명

1. 알파벳 26개를 확인하는 배열을 만든다.

2. 입력받은 단어의 길이만큼 반복문을 돌린다.

 

-1) 나왔던 문자인지 확인한다.

-2) 나왔던 문자라면 바로 전 문자와 같은지 확인하여, 아니면 그룹 단어가 아니라고 체크함

-3) 나왔던 문자가 아니라면 alpha 배열에서 해당 단어를 나왔다고 바꾼 후 다음 단어 탐색

 

3. 단어의 개수만큼 2번 반복

---

✅ 코드

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

int main(void) {
	int n, cnt = 0;
	scanf("%d", &n); // 단어의 개수 입력

	/* 단어의 개수만큼 반복문 */
	for (int i = 0; i < n; i++) {
		char word[101];
		scanf("%s", word); // 단어 입력

		int alpha[26] = { 0, }; // 나왔던 문자인지 판단하기 위해
		int flag = 0;
		for (int j = 0; j < strlen(word); j++) {
			if (alpha[word[j] - 'a'] == 1) { // 이미 나왔던 문자라면
				if (word[j] != word[j - 1]) { // 바로 전 문자와 같지 않다면
					flag = 1; // 그룹 단어 아니기 때문에 탈출
					break;
				}
			}
			else alpha[word[j] - 'a'] = 1; // 나온 문자라고 바꾸기
		}
		if (flag == 0) // 그룹단어라면 cnt++
			cnt++;
	}
	printf("%d\n", cnt);
	return 0;
}

 

⚡ alpha[ word[j] - ‘a’ ] = 1이 의미하는 것은?

: 해당 문제에서 단어는 소문자로만 이뤄졌다고 했기 때문에 다음과 같이 사용할 수 있음.

ex) banana => word[0] = ‘b’

 

- word[0] - ‘a’ = ‘b’ - ‘a’

: 아스키코드 값으로 98 – 97 = 1이 나옴

 

- alpha[1] == ‘b’

: alpha[1] = 1로 바꿔 나왔던 단어라고 표시함

---

https://github.com/2hyunjinn/Baekjoon/blob/main/Baekjoon_1316.cpp

GitHub - 2hyunjinn/Baekjoon