[c++] 백준 1316: 그룹 단어 체커

문제를 푸는데 시간을 꽤 소모하였고 때문에 이때의 생각을 남겨두는 것이 좋을 것 같아서 남긴다.

 

우선 제출 코드는 아래와 같다.

 

#include <iostream>

int main() {

	int N;
	std::cin >> N;

	std::string* s = new std::string[N];

	for (int a = 0; a < N; a++) {
		std::cin >> s[a];
	}
	int count = 0;

	bool flag = false;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < s[i].length(); j++) {

			int last_idx = j;
			for (int k = j; k < s[i].length(); k++) {
				if (s[i][j] == s[i][k]) {
					if (k - last_idx >= 2) {
						flag = true;
						break;
					}
					else {
						last_idx = k;
					}
				}
			}
			if (flag) {
				count++;
				flag = false;
				break;
			}

		}
	}

	std::cout << N - count << "\n";

	delete[] s;

}

 

문제풀이 :

문제풀이는 그냥 brute force 방법을 사용하였다.

그냥 문자열이 있을 때 처음 문자부터 마지막 문자까지, 그리고 두번째 문자부터 마지막 문자까지, ..., 마지막 문자부터 마지막 문자까지 다 비교를 하게 된다. 

0 1 2 3 4 5 6

   1 2 3 4 5 6

      2 3 4 5 6

         3 4 5 6

            4 5 6

               5 6

                  6

 

즉 맨 처음의 문자가 기준문자가 되고 차례대로 마지막 문자까지 비교를 하게 된다.

이때 last_idx 변수는 가장 최근에 기준 문자와 비교 문자가 같을 때 비교 문자의 index를 가져온다. 따라서 만약 index가 2이상 차이가 난다면 몇 개의 문자를 건너 뛰고 다시 같은 문자가 나오는 것이므로 그룹단어가 아니다.

 

이때 flag 변수를 true로 놓고 세번째 반복문에서 빠져나온다. 그리고 두번 째 반복문의 flag 변수 검사에서 flag가 ture일 때 count를 증가시키고 두번 째 반복문을 빠져나온다. 즉, count는 그룹단어가 아닌 문자열을 체크한다. 마지막으로 입력 문자열 개수와 그룹단어가 아닌 문자열의 개수를 빼서 그룹단어가 있는 문자열의 개수를 반환한다.