#include <stdio.h>
int main(void)
{
int n, cnt = 0, i, grouped;
int lastIndex[26] = { 0 };
char c;
scanf("%d%*c", &n);
while(n--)
{
i = 1, grouped = 1;
// while loop: until '\n' entered, get characters one by one for one word
while ((c = getchar()) != '\n')
{
if (grouped)
{
// if the value at an index corresponding to alphabetical order is 2 (or more) less than i
if (lastIndex[c - 'a'] && i - lastIndex[c - 'a'] > 1)
grouped = 0;
else
// store i into index array at an index corresponding to alphabetical order
lastIndex[c - 'a'] = i;
}
i++;
}
if(grouped && i > 1)
cnt++;
for (i = 0; i < 26; i++)
lastIndex[i] = 0;
}
printf("%d", cnt);
return 0;
}
- 로직 자체는 단순했는데 통과가 되지 않아 반례모음집과 게시판, 오류나는 원인 등을 찾다가 겨우 겨우 해결한 문제다.
결론부터 말하면, 단어를 여러번 검사할때마다 관련 변수를 모두 초기화해주었어야 하는데 lastIndex를 초기화하지 않아 버그가 생겼다.
- 문제 접근
- lastIndex 배열
a-z까지의 알파벳 순으로 0열부터 25열까지, 특정 알파벳이 가장 최근 등장한 순서(인덱스+1)를 저장한다.
- grouped (플래그)
그룹단어가 아니란 게 확인된다면 추가적인 조건검사를 하지 않도록 하는 역할
- getchar를 통해 한 글자를 입력 받을 때마다 조건을 확인해서
- 한번이라도 등장한 알파벳인데 바로 직전 알파벳과 같은 알파벳이 아니라면 grouped를 false로 만들고
- 한번도 등장하지 않은 알파벳이거나, 혹은 등장했더라도 바로 직전에 온 알파벳이라면
문자열 내에서 현재 검사하고 있는 문자의 순서를 저장
- for문을 이용한 초기화가 맘에 들지 않아 다른 사람들 코드를 읽어보았더니 lastIndex자체를 루프 안에서 선언하고 있다.
- 확실히 코드를 단순화할 수 있을 것 같은데 무조건 변수 선언(i라 할지라도)은 함수 첫 줄에 하라했던 교수님 때문에 망설여진다 ㅠ 방학 때 질문하면 받아주시려나
- 반례 찾기에 도움이 된 글
