백준 1316 번 문제 풀이 C++ :그룹 단어 체커

#55. 백준 1316번 문제 풀이: 그룹 단어 체커

그룹단어란 각 문자가 같은 문자들은 떨어지지 않고 연속해 있는 경우를 말한다. ccazzzzbb 는 c,a,z,b가 연속, kin k,i,n이 연속이므로 그룹단어. aabbccb는 b 가 떨어진 곳에 위치하므로 그룹단어가 아니다. 단어 N개를 입력받아 그룹단어의 개수를 출력하시오. 입력: 첫줄에 단어의 개수 N, 둘째 줄은 N개의 단어가 한줄씩 들어온다. 단, N≤100, 알파벳은 소문자이다. 출력: 그룹단어의 개수

입력/출력

--입력--
3
happy
new
year
--출력--
3
--입력--
4
aba
abab
abcabc
a
--출력--
1

문제풀이+해설

문자열을 받아 문자단위로 구분해서 체크할 수 있어야 풀리는 문제이다.
그리고 문자의 반복 여부를 체크할 수 있는 알고리즘이 있어야 한다.

그룹단어를 체크하는 알고리즘은 아래와 같을 것이다.
--
이전문자 = 처음문자
루프 (두번째 문자부터 글자수만큼):
  if (이전문자가 비교문자와 다르면) :
    if (비교문자가 체크문자열에 있다면) : 그룹문자 아님
    이전문자 = 비교문자
    체크문자열에 비교문자 등록
루프 끝
--

체크문자열 활용 방법
 1.체크문자열은 알파뱃갯수(26) 크기의 배열을 만들고 0으로 초기화 한다.
 2.문자가 있으면 체크문자열에서 해당하는 문자값을 0로 설정
 3.새로운 비교문자가 체크문자열에서 1값을 가졌다면 그룹단어가 아니다


  문자에 해당하는 배열에 1 값 설정

code sol.

코드편집/실행

#include <iostream>
using namespace std;

// 그룹단어 인지 체크하는 함수
int is_group_word(string wd) { //wd: 그룹단어인지 체크할 단어 리턴: 그룹단어 1, 아니면 0
  int i, cnum;
  int ck[26] = {0}; // 알파벳 사용여부 기록할 배열
  int anum = (int)'a'; //'a' 문자의 아스키 코드값. 
  int l = wd.length(); // 단어 문자수
  char c0 = wd[0]; // 첫글자를 초기값으로 대입
  for(i = 1; i < l; i++) { // 두번째 글자부터 비교 시작
    if(c0 != wd[i]) { // 새로운 문자가 시작되면
      cnum = (int)wd[i] - anum; 
      // 현재 문자의 아스키코드 에서 'a'의 아스키코드를 빼면 알파벳 순서값이 된다.
      if(ck[cnum] == 1) { // 이미 해당 알파벳이 사용되었었다면 그룹단어가 아님.
        return 0; // 그룹단어가 아니므로 더 비교할 필요가 없으니 빠져나간다.
      } else { // 사용했던 문자가 아니면 
        ck[(int)c0-anum] = 1; // 이전 문자의 순서 위치에 사용문자로 등록
        c0 = wd[i]; // 이전 문자는 현재 문자로 변경
      }
    }
  }
  return 1; // 루프를 통과했다면 그룹단어. 1리턴
}

int main() {
  int i, n;
  int count = 0; // 그룹단어 개수  카운트
  string wd; // 단어저장용 변수.
  cin >> n; // 단어개수를 입력받아 정수로 변환 후 대입
  for(i = 0; i < n; i++) { // n만큼 반복
    cin >> wd; // 단어 한개를 받아옴
    if(is_group_word(wd)==1) count++; // 그룹단어라면 개수 카운트 증가
  }
  cout << count; // 카운트 출력
  return 0;
}