[C++] 백준 알고리즘 1316번 그룹 단어 체커

문제

: 같은 알파벳이 나온다면 무조건 연속해야한다.

그러한 문자열의 갯수 출력

 

예시

:

11
happy
new
year
aba
abab
abcabc
a
limi
abbbbbba
cbalsl
bb

를 입력한다면 출력이 5가 되어야 한다.

왜냐하면 그룹단어는 happy new year a bb 이기 때문

 

다들 알파벳 배열 만들어서 하던데

나는 다른 방법을 이용해보고 싶어서

마음대로 풀다가 더 고생한 느낌이다,,

 

아이디어

: 주석참고

1. 문자열 총 갯수 = total

2. 그룹 단어가 아닌게 발견되면 total--

3. i번째 문자열의 j번째 알파벳을 j++해나가며 같은 알파벳 있는지 체크

4. 연속하면서 같은 알파벳은 pass, 연속하지 않은데 같은 알파벳이면 total-- 하기

5. 한 문자열 체크 했으면 i+1번째 문자열도 체크

6. 3~5 반복

 

결론 <<

전체 문자열 갯수 - 그룹 단어가 아닌 문자열 갯수 = 그룹 단어의 갯수

 

그런데

예기치 못한 변수들에서 오류가 나서

디버깅을 수십번 돌리고 모든 오류를 잡았다

그리고 겨우 맞았습니다가 떴다

 

내 코드가 썩 효율적이지 않은건

직감으로 알 수 있다..

 

백준 알고리즘 1316번 그룹 단어 체커

 

#include<iostream>
#include<vector>

using namespace std;

int main() {
	//n개의 입력을 받자
	int n;
	cin >> n;

	//총 그룹단어의 갯수를 담을 total 변수
	int total = n;
	vector<string> group;
	while (n != 0) {
		string str;
		cin >> str;
		group.push_back(str);
		n--;
	}

	//n개의 스트링이 있다고 하자
	//그 중 한 스트링의 특정 알파벳이
	//연속하지 않으면서 뒤에 재등장한다면
	//그룹 단어가 아니므로 전체 단어수 -1을 한다
	//아닌 것을 -1하다보면 총 그룹단어의 갯수만 남음

	int i, j, k;
	char temp;

	//첫 번째  스트링부터 보고자 함
	for (i = 0; i < group.size(); i++) {
		//i번째 스트링의 첫 번째 알파벳부터 보고자 함
		//마지막 문자열은 비교할 필요 X, 앞과 겹쳤으면 앞에서 걸렸을 터, 따라서 group[i].length()-1
		for (j = 0; j < group[i].length()-1; j++) {
			temp = group[i][j];
			k = j;
			//특정 알파벳과 다른 알파벳이 나올 때 까지 비교
			do {
				k++;
			} while (temp == group[i][k]);

			//기존의 total값 저장.
			//그룹이 아니게되면 total--이 되는데
			//그룹이 아닌게 밝혀진 후의 쓸데없는 비교를 줄이고자 함.
			int temp_total = total;

			//현재 k번째 알파벳과 특정 지은 알파벳이 다름
			while (k < group[i].length()-1) {
				//이후 특정지은 알파벳이 재등장하면
				//그룹단어가 아니니 -1하고 반복문 빠져나오기
				k++;

				if (temp == group[i][k]) {
					total--;
					break;
				}
			}
			//만약 앞에서 그룹단어가 아니라고 판명나면
			//이 스트링은 더 이상 볼 필요 없음, break
			
			//한 알파벳에 대해 그룹단어이면
			//그 다음 단어도 계속 체킹해야하므로 반복문 계속
			if(total != temp_total)
				break;
		}
	}
	cout << total << endl;
}