[백준] 1316 풀이

오랜만에 알고리즘 문제를 풀어봤다. 문제를 처음 봤을 때는 아무것도 몰랐지만, 계속 끙끙대면 보다보니 풀게 되었다. 

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

1316번: 그룹 단어 체커

 

문자열을 몇개 입력받을 것인지, 입력 받은 문자열의 그룹단어를 어떻게 찾는지, 중복을 어떻게 검사할 것인지, 어떻게 결과를 출력할 것인지...

천천히 생각하면서 차근차근 하다보면(당연한 말) 문제를 해결할 수 있는 열쇠를 얻을 수 있다.

 

아래는 코드다.

물론 이것보다 효율적인 코드는 많겠지만 답을 보지 않고 온전히 내 머리로만 풀었기 때문에 더욱 의미있는 코드라고 생각된다.

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
	int count; // 문자열의 개수를 담을 변수
	cin >> count;

	char str[101]; // 각 문자열의 최대 길이를 담을 변수
	int result = 0; // 결과 출력에 사용할 변수
    
	// 단어의 중복 처리를 위해 사용할 변수이다.
	// 이 배열이 가장 중요한 포인트이다. alpha를 이용해서 입력받은 문자열의 알파벳의 개수를
	// 전부 다 세고, 세 번째 while문에서 사용하는 걸 볼 수 있다. 자세한 내용은 밑에서...
	int alpha[26] = { 0 };
	for (int i = 0; i < count; i++)
	{
		cin >> str;
		int c = 0;
		alpha[26] = { 0 }; // 초기화를 해주는 이유는 다음 루프에서도 사용하기 위해서
		while (str[c] != '\0') { // 각 알파벳의 개수를 셈
			alpha[str[c] - 97]++;
			c++;
		}
		int j = 0; // 배열의 접근하기 위한 요소
		while (j < strlen(str)) { // 모든 배열에 접근을 위한 반복문
			int wordCheck = 0; // 단어 중복 처리를 위한 변수
			int k = 0;
			// 각 알파벳의 개수만큼 반복문을 돌린다. 이렇게 하는 이유는 각 단어마다
			// 중복처리를 위함이다. 단어가 만약에 "ddddeeeedffff" 이런식으로 입력이
			// 들어오면 알파벳 'd'의 개수는 5개이지만 연속되는 'd'의 개수는 4개다. 
			// 이를 이용해서 만약 알파벳의 개수만큼 반복을 했는데 wordCheck, k의 값이
			// 똑같지 않다면 중간에 단어의 연속성이 끊어진 것이다.
			while (k < alpha[str[j] - 97]) { 
				if (str[j] == str[j + k]) 
					wordCheck++;
				k++;
			}
			// 이렇게 체크를 해준다.
			// 한 단어의 연속성이 확인되었다면, 다음으로 넘어가는 식이다.
			if (wordCheck == k) j += k;
			else break;
		}
		if (j == strlen(str)) result++;
	}
	cout << result;
}