백준 1316번: 그룹 단어 체커

- 문제 주소: https://www.acmicpc.net/problem/1316

- solved.ac 기준 실버 5

1316번: 그룹 단어 체커

문제풀이 초안

- 제출한 답: C++로 작성, 1988KB

- 결과: 정답

#include <string>
#include <iostream>

using namespace std;

bool isGroupWord(string str) {
	int i = 0;
	while (i < str.length() - 1) {
    	// 인접한 두 문자가 같은 문자일 경우 스킵
		if (str.at(i) == str.at(i + 1)) {
			i++;
		} else {
			for (int j = i + 1; j < str.length(); j++) {
            	// 연속해서 나타나지 않는 경우 false 반환
				if (str.at(i) == str.at(j))
					return false;
			}
			i++;
		}
	}
	return true;
}

int main() {
	int n, count;
	string* str;

	// 단어 개수 입력받고 str에 배열 동적할당
	cin >> n;
	str = new string[n];

	// 단어 입력
	for (int i = 0; i < n; i++) {
		cin >> str[i];
	}
	
	count = 0;
	
    // 단어가 그룹 단어이면 count를 1 증가시킴
	for (int i = 0; i < n; i++) {
		if (isGroupWord(str[i])) count++;
	}

	cout << count << endl;
    
	delete[] str;
	return 0;
}

시간복잡도를 최적화한 풀이

- 이미 등장한 알파벳인지를 판단하는 불 타입 배열 선언

- 제출한 답: C++로 작성, 1988KB

- 결과: 정답

#include <string>
#include <iostream>

using namespace std;
const char LITTLE_A = 'a';

bool isGroupWord(string str) {
	// 단어 중복을 체크할 불 배열 선언
	bool* wordCheck = new bool[26]{ false, };
	wordCheck[str.at(0) - LITTLE_A] = true;
	for (int i = 1; i < str.length(); i++) {
		// 이미 등장한 알파벳인지 체크 
		if (!wordCheck[str.at(i) - LITTLE_A])
			wordCheck[str.at(i) - LITTLE_A] = true;
		// 만약 이미 등장한 알파벳이라면 앞자리의 알파벳과 동일한지 체크
		else
			if (str.at(i) != str.at(i - 1)) return false;
	}
	delete[] wordCheck;
	return true;
}

int main() {
	int n, count;
	string* str;

	// 단어 개수 입력받고 str에 배열 동적할당
	cin >> n;
	str = new string[n];

	// 단어 입력
	for (int i = 0; i < n; i++) {
		cin >> str[i];
	}

	count = 0;

	// 단어가 그룹 단어이면 count를 1 증가시킴
	for (int i = 0; i < n; i++) {
		if (isGroupWord(str[i])) count++;
	}

	cout << count << endl;

	delete[] str;

	return 0;
}