문제: AtCoder ABC 237 C — kasaka English · [한국어] · 日本語
문자열 앞에 a만 덧붙일 수 있으므로 문자열 끝의 문자는 바꿀 수 없습니다. 문자열 앞부분에 연속된 a가 몇 개인지(leadingA), 뒷부분에 연속된 a가 몇 개인지(trailingA) 셉니다. leadingA > trailingA라면 앞의 a들을 뒤에서 맞춰 줄 만큼의 a가 부족하므로 회문을 만들 수 없습니다.
그렇지 않다면 trailingA - leadingA개의 a를 앞에 추가해 두 연속 구간을 균형 맞출 수 있습니다. 그러면 앞뒤의 a 구간을 제외한 가운데 부분이 이미 회문이어야 합니다. 양쪽에서 a를 건너뛰고 남은 부분을 투 포인터로 비교합니다. 두 포인터가 교차하면 가운데 부분이 비었거나 문자가 하나뿐이므로 회문입니다.
문자열 전체가 a인 경우(가운데가 빈 경우)와 양 끝에 a가 없는 경우(문자열 전체를 검사)도 처리합니다. 시간 복잡도는 O(|S|), 추가 공간 복잡도는 O(1)입니다.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
String s = input.readLine();
int left = 0;
while (left < s.length() && s.charAt(left) == 'a') {
left++;
}
int right = s.length() - 1;
while (right >= 0 && s.charAt(right) == 'a') {
right--;
}
int leadingA = left;
int trailingA = s.length() - 1 - right;
if (leadingA > trailingA) {
System.out.println("No");
return;
}
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
System.out.println("No");
return;
}
left++;
right--;
}
System.out.println("Yes");
}
}