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

 

 이 문제는 STL의 set을 이용하여 푸니 그닥 어렵진 않았는데, 구현의 난이도를 고려하여 실버 5로 평가되어 있는 듯하다. 글자가 하나만 나와도 연속해서 나온다고 판단하므로 글자의 등장 횟수는 중요하지 않고, 글자가 다른 위치에서 또 나오냐 마냐가 중요한 문제이다. 그래서 숫자를 세지 않으면서 나온 글자들의 정보를 저장할 수 있는 자료구조로 집합을 선택했다.

 

 코드를 확인해보자.

 

#include <iostream>
#include <set>
using namespace std;

int main()
{
    int N;
    cin >> N;

    int count = 0;
    for (int _ = 0; _ < N; _++)
    {
        set<char> characters;

        string temp;
        cin >> temp;

        int i = 0;
        bool isGroupWord = true;
        while (i < temp.length())
        {
            if (characters.find(temp[i]) == characters.end())
            {
                characters.insert(temp[i]);
                i++;

                while (temp[i] == temp[i - 1] && i < temp.length()) i++; 
            }
            else
            {
                isGroupWord = false;
                break;
            }
        }
        if (isGroupWord) count++;
    }

    cout << count;

    return 0;
}

 Group word의 개수는 int형 변수 count에 저장한다. 그 다음 반복 변수를 _으로 둔 iteration N회의 알고리즘을 서술해 보겠다.

 

1. 단어에 등장하는 알파벳들을 저장할 집합 set<char> characters를 선언한다.
2. string 객체 temp에 단어를 입력 받는다.
3. temp의 글자를 처음부터 읽어나가기 위해 인덱스로 사용할 int형 변수 i를 선언하고 0으로 초기화한다.
4. 단어가 group word인지 판별하기 위해 플래그 isGroupWord를 선언하고 true로 초기화한다. 반례 등장 시 false로 바꾼다.
5. 첫 번째 while loop는 글자를 전부 읽었다면 종료된다. 다음은 while loop 안에서의 동작이다.
   1. set 객체는 find 메소드로 원소를 찾을 수 있는데, 해당 원소가 존재하지 않는다면 객체의 end iterator를 반환한다. 그래서 첫 번째 조건은 이번에 읽은 글자 c가 집합에 존재하지 않는 경우, 즉 처음 등장한 경우를 나타낸다. 이때는 집합에 해당 글자를 삽입하고, 인덱스 i를 1 올려서 c의 다음 글자를 가리키게 한 후 c가 연속될 경우 다음 while loop를 통해 c가 아닌 최초의 글자에 인덱스를 놓거나, c가 마지막 글자까지 이어질 경우 i를 끝까지 올려 다음 iteration을 막는다.
   2. 두 번째 조건은 집합에 이번에 읽은 글자 c가 이미 집합에 존재하는 경우이다. 첫 번째 조건 내의 while loop 덕분에 연속된 글자를 읽으면서 두 번째 조건이 성립하는 경우는 없다. 예를 들어 "aaaab"에서는 0번째 a를 읽은 iteration에서 단번에 i가 4로 증가하고, "aaaaba"에서는 b까지 읽은 후 i가 5가 되었을 때 집합에는 이미 a가 존재하여 characters.find(temp[5])가 characters.end()를 리턴하지 않기 때문에 두 번째 조건이 성립하게 되는 것이다. 이때는 플래그 isGroupWord를 false로 바꾸고 즉시 이번 단어 읽기를 종료한다.