17609번: 회문
각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.
www.acmicpc.net
N이 10만개니 lcs로는 해결 못합니다..
투 포인터로 하나하나 확인해줍니다.
왼쪽 인덱스를 0, 오른쪽 인덱스를 ch.length - 1로 두고
문자열의 끝 단어끼리 비교를 합니다.
1. 끝 단어가 같을 때
- 왼쪽, 오른쪽 인덱스 모두 다음 인덱스를 확인합니다.
2. 끝 단어가 다를 때
- 왼쪽 인덱스를 옮겨줄 때와 오른쪽 인덱스를 옮겨줄 때를 각각 확인합니다.
저는 투포인터를 두번 사용하여 왼쪽 인덱스를 옮길 때, 오른쪽 인덱스를 옮길 때 다른 값의 min값으로 답을 출력하였습니다.
|
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static char ch[];
static void func() {
int l = 0;
int r = ch.length - 1;
int ans = 0;
int cnt = 0;
while (l < r) {
if (ch[l] == ch[r]) {
l++;
r--;
} else {
cnt++;
l++;
}
if (cnt == 2)
break;
}
ans = cnt;
l = 0;
r = ch.length - 1;
cnt = 0;
while (l < r) {
if (ch[l] == ch[r]) {
l++;
r--;
} else {
cnt++;
r--;
}
if (cnt == 2)
break;
}
ans = Math.min(ans, cnt);
sb.append(ans).append("\n");
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
ch = st.nextToken().toCharArray();
}
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine());
int tc = Integer.parseInt(st.nextToken());
while (tc-- > 0) {
input();
func();
}
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > Two-Pointer' 카테고리의 다른 글
| boj 1253 좋다 (0) | 2021.10.21 |
|---|---|
| boj 9024 두 수의 합 (0) | 2021.10.21 |
| boj 2559 수열 (0) | 2021.02.12 |
| boj 1806 부분합 (0) | 2021.01.22 |
| boj 2003 수들의 합 2 (0) | 2021.01.22 |