백준(BOJ) 1316 그룹 단어 체커 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/1316

1316번: 그룹 단어 체커

문제 풀이에 이용된 알고리즘: 단순 구현

 

주어진 단어가 그룹 단어인지 체크하는 것이 목적이다. 그룹 단어인 지 파악하기 위해서, 단어 내에서 어떤 철자가 등장한 적이 있는 지를 visited 배열에 기록한다.

 

단어를 한 글자씩 뜯어보며, 이미 한 번 등장했던 철자가 다시 등장했는데, 이전 철자와의 연속성이 없다면 그룹 단어가 아닌 것으로 판단한다.

 

문제 자체는 어렵지 않지만, 철자를 배열에 표현하기 위해 "철자 <-> 인덱스"의 변환이라던지(알파벳 a ~ z를 0 ~ 26으로 표현하는 가장 간편한 방법은 어떤 char 변수에서 -'a'를 빼주는 것이다.), 철자의 연속성 확인을 위해서 prev와 cur이라는 두 개의 변수를 이용하는 등의 수단을 구현하는 것이 어려운 문제였다고 생각된다.

 

/* BOJ 1316 그룹 단어 체커 */
/* 단순 구현.. */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string.h>
#include <cstring>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int n;
bool visited[26];
vector<string> words;
 
bool is_GroupWord(string word)
{
    char prev_char = 'a', cur_char = 'a'; // 단순 초기화 dummy 값 'a'
    for (int i = 0; i < word.length(); i++)
    {
        cur_char = word[i];
 
        // 이미 한 번 등장했던 철자가 다시 등장하고, 이전 철자와의 연속성이 없다면
        if (visited[cur_char - 'a'] && prev_char != cur_char)
            return false; // 그룹 단어가 아니다
        
        if (!visited[cur_char - 'a']) // 새로운 철자가 등장하면
            visited[cur_char - 'a'] = true; // 등장했다고 표시
 
        // 다음 for문 실행시 이전 철자는 곧 현재 for문 step에서의 철자
        prev_char = cur_char; 
    }
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    freopen("input.txt", "r", stdin);
 
    int cnt = 0;
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        memset(visited, 0x00, sizeof(visited));
        string word;
        cin >> word;
        if (is_GroupWord(word))
            cnt++;
    }
 
    cout << cnt << endl;
 
    return 0;
}