[C++] 백준 1316번 그룹 단어 체커

1. 문제이해

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

1316번: 그룹 단어 체커

 

그룹단어란, 단어에 존재하는 모든 문자에 대해 각 문제가 연속해서 나타나는 단어이다.

단어 N개가 주어질 때, 이중 그룹단어의 개수를 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

N개의 단어를 입력받아, 그 중 그룹단어의 개수를 출력하는 것이 목표이다.

그룹 단어를 예시를 들어 설명하자면, ccaabb, aaeef, ahcfs 등과 같이

단어를 이루는 각 문자들이 연속해서 나타내는 단어이다.

ccaabb 같은 경우, c가 연속해서 나타나고, a와 b 또한 연속적으로 나타난다.

ahcfs 는 a, h, c, f, s 단어가 1번씩만 연속적으로 나타나기 때문에 그룹 단어이다.

 

그룹 단어가 아닌 단어들의 예로는, cabcab, ararar, sjsfe 등이 있다.

cabcab 같은 경우, c라는 단어가 맨 처음 등장한 후 연속적으로 나타나지 않고, 4번째에 다시 나타난다.

a와 b도 마찬가지로 불연속적으로 나타난다.

이처럼, 단어 안에 불연속적으로 나타나는 문자가 하나라도 있다면 그룹 단어가 아니다.

 

 

그렇다면, 입력받은 단어가 그룹단어인지 아닌지 어떤식으로 판단해야할까?

필자는 단어에서 알파벳 문자의 출현 유무를 나타내는 bool형 배열을 선언하고, (기본값은 모두 false)

단어의 앞에서부터 한 문자씩 체크해나가며, 출현한 단어의 순서에 해당하는 배열 값을 true 값으로 바꾸어주었다.

(bool alphabet[26] = { false, };  이라는 배열을 두고,

만약 a라는 문자를 접하면, a에 해당하는 순서의 배열 값을 true로 바꾸어준다.

여기서 문자에 해당하는 순서는 아스키 코드값을 이용했다.

아스키 코드에서 a~z 는 97~122 에 해당. 각 문자의 아스키 값에서 97을 빼준 값을 배열의 순서값으로 정했다.)

 

위와 같은 작업을 통해, 만약 1. 단어의 n번째 문자가 n-1번째 문자와 같지 않고(연속하지 않고),

2. n번째 문자에 해당하는 배열 값이 true 라면(이미 나왔던 문자라면),

불연속한 문자가 있다고 판단. 그룹단어가 아니라고 판단해주는 식의 알고리즘을 구현했다.

 

이를 이용해 구현한 코드는 아래와 같다.

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

int main() { 
	int N;                                // 입력받을 단어의 개수
	string word;                          // 입력받은 단어
	int count = 0;                        // 그룹 단어가 아니라면 카운트

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> word;
        
		// 단어에서 알파벳 문자의 출현유무를 나타내는 배열 (출현없으면 false)
		bool alphabet[26] = { false, };        
		alphabet[(int)(word[0]) - 97] = true;  // 첫번째 단어값을 true로 설정

		for (int i = 1; i < word.size(); i++) {
        
			// 1. i번째 문자가 i-1번째 문자와 같으면 연속이므로 넘어간다.
			if (word[i] == word[i - 1]) {
				continue;
			}
            
			// 2. i번째 문자가 i-1번째 문자와 같지 않고, (연속하지 않고)
			//    해당 배열값이 true라면 (이미 나왔던 문자라면)
			else if(word[i] != word[i - 1] 
            		&& alphabet[(int)(word[i]) - 97] == true){
				count++;	// 그룹단어가 아니므로 카운트
				break;
			}
            
			// 3. 위의 두 경우에 해당하지 않는 경우
			//    처음 등장한 문자인 경우
			else {
				alphabet[(int)(word[i]) - 97] = true;
			}
		}
	}

	// 그룹 단어의 개수 = 전체단어의 개수 - 그룹단어가 아닌 단어의 개수
	cout << N - count;

	return 0;
}

위의 2. 문제풀이에서 도출한 방법을 이용해 구현한 코드이다.

각 단어를 입력받을 때마다, bool alphabet[26] = { false, };  이라는 배열을 두어 false값으로 초기화하고,

첫번째 문자는 true처리, 2번째 문자부터 아래와 같은  기준에 따라 for문을 진행한다.

 

1. 단어의 i번째 문자가 i-1번째 문자와 같으면 연속이므로 넘어간다.

 

2. 단어의 i번째 문자가 i-1번째 문자와 같지 않고, (연속하지 않고)
i번째 문자에 해당하는 배열값이 true라면 (이미 나왔던 문자라면)

해당 단어는 그룹단어가 아니므로 count하고, for문을 빠져나가 다음 단어를 입력받는다.

 

3. 위의 두 경우에 해당하지 않는 경우, 즉 처음 등장한 문자인 경우

문자에 해당하는 출현 배열의 값을 true로 설정한다.

 

위와 같은 과정을 모두 거친 뒤, count 값에는 그룹단어가 아닌 단어의 개수가 저장되어있으므로

(전체 단어의 개수 - 그룹단어가 아닌 단어의 개수)를 해주어 그룹 단어의 개수를 출력해주었다.

 

주석 없는 코드는 바로 왼쪽 아래의 더보기 확인 바랍니다.😊

<주석 없는 코드>

#include <iostream>
using namespace std;

int main() { 
	int N;                   
	string word;                       
	int count = 0;                      

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> word;
		bool alphabet[26] = { false, };        
		alphabet[(int)(word[0]) - 97] = true; 

		for (int i = 1; i < word.size(); i++) {
			if (word[i] == word[i - 1]) {
				continue;
			}
			else if(word[i] != word[i - 1] 
            		&& alphabet[(int)(word[i]) - 97] == true){
				count++;	
				break;
			}
			else {
				alphabet[(int)(word[i]) - 97] = true;
			}
		}
	}

	cout << N - count;

	return 0;
}

 

 

---

질문과 지적은 언제나 감사하게 받고있습니다!😊