[코딩테스트 31일차] BAEKJOON 1316번 : 그룹 단어 체커

[BAEKJOON 1316번 : 그룹 단어 체커]

[문제]

---

[고찰]

저는 해당 문제를 입력받은 단어를 1의 인덱스부터 단어의 길이만큼 반복하면서

앞에 글자와 다를 때, 그 전에 등장한 적이 있는 단어인지를 확인하는 방식으로 직접 비교하여 코드를 구성하였습니다.

 

다른 분들의 풀이를 살펴보니, 페크를 위해 등장할 문자들을 기록한 bool 배열을 사용하였습니다.

 

저도 배열을 떠올리기는 했으나, bool 타입이 아닌 int 타입으로 배열을 선언해 등장한 글자들을 체크하려 했었습니다.

하지만 int 타입 배열을 통해 글자가 몇 번 등장했는지 기록하더라도 해당 문제를 해결할 방법은 없기에, 배열을 활용하는 아이디어는 접었습니다.

 

그래서 bool 배열을 활용하는 방식을 정리하고자 합니다.

 

아래는 제가 작성한 코드입니다.

#include <iostream>
#include <string>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int count = 0;
	bool isGroup = true;

	int n;
	cin >> n;

	while (n--)
	{
		string word;
		cin >> word;
		
		isGroup = true;

		if (word.size() == 1)
		{
			count++;
		}
		else
		{
			for (int i = 1; i < word.size(); i++)
			{
				if (word[i] != word[i - 1])
				{
					for (int j = 0; j < i; j++)
					{
						if (word[j] == word[i])
						{
							isGroup = false;
							break;
						}
					}
				}
			}

			if (isGroup)
				count++;
		}
	}

	cout << count;

	return 0;
}

---

[개념]

제가 푼 방식도 논리 자체는 정확하고, 직접 비교로 이해하기도 쉽습니다.

다만 이중 for문을 사용하여 앞쪽을 다시 스캔하기 때문에, 문자 길이가 길어질수록 최악의 경우, O(n²)의 성능이 나올 수 있습니다.

---

bool 배열 활용

bool seen[26] = { false };

알파벳 26개의 개수를 갖는 bool 배열을 생성합니다. 이때 기본값은 false로 선언합니다.

 

char prev = 0;

먼저 char prev를 선언합니다. prev는 이전 글자를 저장할 변수입니다.

0으로 선언한 이유는, ASCII 상 널 문자로, 실제 알파벳이 아니므로, 첫 글자를 무조건 새 글자로 취급하기 위한 초기화입니다.

 

for (char c : word)

범위 기반 for문을 통해, word의 모든 문자를 하나씩 c에 넣어가며 반복합니다.

 

if (c != prev)

현재 글자 c가 이전 글자 prev와 다를 때를 체크해줍니다.

 

if (seen[c - 'a'])
    return false;

seen[ c - 'a' ] 는 현재 글자 c에 대한 seen 배열이 true인지를 확인합니다.

true라는 것은 과거에 등장했었는데, 현재 다시 새롭게 등장했다는 의미로, 그룹 단어가 아닌 것이기 때문에 false를 반환합니다.

 

seen[c - 'a'] = true;

현재 글자 c가 등장했다는 것을 seen 배열에 true로 저장하는 것으로 기록합니다.

 

prev = c;

현재 글자를 prev에 저장해두어 다음 반복에서 연속 여부를 판단할 수 있게 합니다.

---

위의 코드들을 합하여 isGroupWord 함수를 만들면 아래와 같습니다.

bool isGroupWord(const string& word)
{
    bool seen[26] = { false };
    char prev = 0;

    for (char c : word)
    {
        if (c != prev)
        {
            if (seen[c - 'a'])
                return false;
                
            seen[c - 'a'] = true;
            prev = c;
        }
    }

    return true;
}

 

이제 main 함수에서 isGroupWord(word)가 true라면 count를 1 더해줘서, 최종적으로 그룹 단어가 몇 개인지를 알 수 있습니다.

 

bool 배열을 활용한 방식은 제가 사용한 방식과 다르게, 한 번만 반복하면서 문자가 재등장했는지 체크하기 때문에 O(n)의 성능을 가집니다. 즉, 입력 단어 길이에 선형으로 처리가 가능합니다

---

[정리]

좀 더 집요하게 배열에 관한 아이디어를 생각했다면, bool 배열을 활용하는 것을 떠올릴 수 있었을텐데 좀 아쉽습니다.

물론 제 답변이 틀린 것은 아니지만, 보다 정답인 쪽에 가까운 코드를 보면 부족한 점을 느끼게 됩니다.

 

더욱 집요하게 문제를 풀면서 부족한 점을 더 극복해야겠습니다.

---

[Solution]

#include <iostream>
#include <string>

using namespace std;

bool isGroupWord(const string& word)
{
    bool seen[26] = { false }; 
    
    char prev = 0;
    for (char c : word)
    {
        if (c != prev)
        {
            if (seen[c - 'a'])
                return false;
                
            seen[c - 'a'] = true;
            prev = c;
        }
    }

    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, count = 0;
    cin >> n;

    while (n--)
    {
        string word;
        cin >> word;

        if (isGroupWord(word)) 
            count++;
    }

    cout << count;
    
    return 0;
}