스러피
면접 대비시간 제한2초메모리 제한512 MB
대문자 문자열이 Slimp 뒤에 Slump가 이어지는 Slurpy인지 판별한다. 두 요소는 재귀 문법 규칙으로 정의된다.
문제
스러피(Slurpy)는 아래에서 정의하는 규칙을 만족하는 문자열이다. 문자열을 읽어 스러피인지 판정하는 프로그램을 작성한다.
먼저 스럼프(Slump)는 다음 규칙을 만족하는 문자열이다.
- 첫 글자는 'D' 또는 'E'이다.
- 첫 글자 뒤에 'F'가 한 개 이상 연달아 온다.
- 그 'F' 뒤에는 또 다른 스럼프가 오거나 'G' 한 글자가 온다. 따라서 스럼프는 언제나 'G'로 끝난다. 예를 들어 DFFEFFFG는 'D'로 시작해 'F'가 두 개 이어지고, 그 뒤에 또 다른 스럼프 EFFFG가 온다. 같은 규칙으로 EFFFG도 스럼프다.
- 위 규칙으로 만들 수 없는 문자열은 스럼프가 아니다.
스림프(Slimp)는 다음 규칙을 만족하는 문자열이다.
- 첫 글자는 'A'이다.
- 길이가 2인 스림프라면 두 번째 글자는 'H'이다.
- 길이가 3 이상인 스림프라면 다음 두 형태 중 하나다.
- 'A' + 'B' + 스림프 + 'C'
- 'A' + 스럼프 + 'C'
- 스림프의 길이는 2 이상이고, 위 규칙으로 만들 수 없는 문자열은 스림프가 아니다.
스러피는 스림프 하나 뒤에 스럼프 하나를 이어 붙인 문자열이다.
분류 예시는 다음과 같다.
- 스럼프: DFG, EFG, DFFFFFG, DFDFDFDFG, DFEFFFFFG
- 스럼프가 아닌 문자열: DFEFF, EFAHG, DEFG, DG, EFFFFDG
- 스림프: AH, ABAHC, ABABAHCC, ADFGC, ADFFFFGC, ABAEFGCC, ADFDFGC
- 스림프가 아닌 문자열: ABC, ABAH, DFGC, ABABAHC, SLIMP, ADGC
- 스러피: AHDFG, ADFGCDFFFFFG, ABAEFGCCDFEFFFFFG
- 스러피가 아닌 문자열: AHDFGA, DFGAH, ABABCC
입력
첫 줄에 문자열의 개수 이 주어진다. 은 이하의 양의 정수다. 다음 개의 줄에 문자열이 한 줄에 하나씩 주어진다. 각 문자열은 길이가 이하이고 알파벳 대문자로만 이루어져 있다.
출력
첫 줄에 SLURPYS OUTPUT을 출력한다. 이어서 입력 순서대로 각 문자열이 스러피면 YES를, 스러피가 아니면 NO를 한 줄에 하나씩 출력한다. 마지막 줄에 END OF OUTPUT을 출력한다.