백준 1316 c++ "그룹 단어 체커" -PlusUltraCode-

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

 

[필자 사고]

처음에 str.find를 이용하여 풀가도 생각했지만 

부르스트 알고리즘을 적용하여 O(n2)으로 문제를 해결했다.

간단한 문자열 문제라서 프로그래밍적 사고를 키우는데 좋은 문제였다.

[코드 해설]

1. 입력 처리 (Input 함수)

• 먼저 N을 입력받는다. 이는 주어진 단어의 개수이다.
• N개의 단어를 입력받아 vector<string> arr에 저장한다.

2. 그룹 단어 판별 (checkGroupWords 함수)

• 주어진 문자열이 그룹 단어인지 검사하는 함수이다.
• 문자열을 처음부터 끝까지 순차적으로 확인하며, 같은 문자가 연속해서 나타나는지 확인한다.
• 특정 문자가 등장한 이후에 다른 문자가 나타났다가 다시 해당 문자가 나오면 그룹 단어가 아니므로 1을 반환한다.
• 모든 검사를 통과하면 그룹 단어이므로 0을 반환한다.

3. 그룹 단어 개수 계산 (Game_Start 함수)

• checkGroupWords 함수를 이용해 그룹 단어가 아닌 단어의 개수를 구한다.
• 총 단어 개수에서 그룹 단어가 아닌 단어 개수를 빼서 그룹 단어의 개수를 출력한다.

[소스 코드]

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

int N;
vector<string> arr;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		arr.push_back(str);
	}
}

int checkGroupWords(string str) {
	for (int i = 0; i < str.size(); i++) {
		bool flag = false;
		for (int k = i + 1; k < str.size(); k++) {
			if (str[i] == str[k]) {
				if (flag == true) {
					return 1;
				}
				continue;
			}
			else {
				flag = true;
			}
		}
	}
	return 0;
}

void Game_Start() {

	int resultCount = 0;

	for (int i = 0; i < N; i++) {
		resultCount += checkGroupWords(arr[i]);
	}

	cout << N-resultCount;
}

int main(void) {
	Input();
	Game_Start();
}