8913번 - 문자열 뽑기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 1135 | 358 | 256 | 36.209% |
문제
a와 b로만 이루어진 문자열 s이 있다. 그룹은 같은 글자로 이루어진 가장 긴 연속 부분 문자열이다. 길이가 2 이상인 s의 모든 그룹 g는 제거할 수(뽑을 수) 있고, 남은 왼쪽 부분과 오른쪽 부분을 연결해서 새 문자열을 만들 수 있다. 이러한 과정은 문자열이 빈 문자열이 되거나, 길이가 2 이상인 그룹이 없을 때 까지 계속한다.
예를 들어, s = babbbaaabb일 때, s에는 그룹이 다섯 개 있다. s는 다음과 같은 단계를 거쳐서 빈 문자열로 바꿀 수 있다. (밑 줄이 그어져 있는 그룹이 뽑히는 그룹)
babbbaaabb → baaaabb → bbb → 빈 문자열
하지만, 아래와 같은 단계를 거친다면, 빈 문자열로 바꿀 수 없다.
babbbaaabb → babbbaaa → baaaa → b
문자열이 주어졌을 때, 적절한 과정을 거쳐 빈 문자로 바꿀 수 있는지 없는지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 a와 b로 이루어진 문자열로 이루어져 있다. 문자열의 길이는 1보다 크거나 같고, 25보다 작거나 같다.
출력
각 테스트 케이스에 대해서, 입력으로 주어진 문자열을 빈 문자열로 바꿀 수 있으면 1을, 없으면 0을 출력한다.
예제 입력 1
3 babbbaaabb aabbaabb abab
예제 출력 1
1 1 0
출처
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2010 B번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호