15770번 - QueryreuQ 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB | 676 | 214 | 132 | 29.596% |
문제
어떠한 문자열에 대해서, 이 문자열을 뒤집어도 같은 문자열이 나온다 이 문자열을 팰린드롬이라 부른다. 예를 들어, "a", "aa", "appa", "queryreuq"와 같은 문자열은 모두 팰린드롬이다.
당신은 빈 문자열 S가 있을 때, 두 가지 연산을 처리해야 한다.
- S의 맨 뒤에 알파벳 소문자를 하나 추가한다.
- S의 맨 뒤에 있는 문자를 제거한다.
각각의 연산을 처리한 후, 당신은 해당 문자열에 있는 팰린드롬 부분문자열의 개수를 세어야 한다. 문자열 S와 1 ≤ i ≤ j ≤ |S|인 정수 i, j에 대해서, S[i, j]를 S의 i번째 문자부터 j번째 문자까지를 포함하는 부분문자열 이라고 정의하자. 당신은 S[i, j]가 팰린드롬인 모든 정수쌍 (i, j)의 개수를 세어서, 이를 출력하여야 한다.
입력
입력은 두개의 줄로 되어있다.
첫 번째 줄에 쿼리의 개수 Q가 주어진다.
두번째 줄에 쿼리가 길이 Q의 문자열로 주어진다. 이 중 i번째 문자 Ki는 i번째 쿼리의 내용을 나타낸다.
Ki는 '-' 이거나, 영어 소문자 ('a', 'b', ..., 'z') 중에 하나이다. (따옴표는 제외한다.)
만약 이 문자가 '-'이라면, S의 맨 뒤의 문자를 제거해야 하며, 영어 소문자라면 S의 맨 뒤에 Ki를 삽입해야 한다.
각 쿼리를 처리한 이후 문자열의 길이가 항상 1 이상이 보장된다.
출력
한 줄에 Q개의 정수를 하나의 공백으로 구분하여 출력한다. 이 중 i번째 정수는 i번째 쿼리에 대한 정답을 의미한다.
제한
- 1 ≤ Q ≤ 10,000
서브태스크 1 (36점)
이 서브태스크는 다음의 조건을 만족한다.:
- Q ≤ 500
서브태스크 2 (64점)
이 서브태스크는 추가 제한 조건이 없다.
예제 입력 1
17 queryreuq--------
예제 출력 1
1 2 3 4 5 7 9 11 13 11 9 7 5 4 3 2 1
출처
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호