https://www.acmicpc.net/problem/17609
1. 유형
문자열
2. 시뮬레이션
- 투포인터 사용
- 두 문자가 다른 경우 왼쪽을 삭제하는 경우와, 오른쪽을 삭제하는 경우가 존재
- 두 경우를 모두 탐색하기 위해 재귀사용
3. 코드
import java.io.*;
import java.util.*;
public class Main {
static String s;
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int T = stoi(st.nextToken());
while (T-- > 0) {
st = new StringTokenizer(in.readLine());
s = st.nextToken();
System.out.println(solve(s, 0, s.length()-1, 0));
}
}
static int solve(String s, int leftpos, int rightpos, int cnt) {
if (cnt == 2) {
return 2;
}
int ret = cnt;
while (leftpos < rightpos) {
if (s.charAt(leftpos) != s.charAt(rightpos)) {
int leftvalue = solve(s, leftpos + 1, rightpos, cnt + 1);
int rightvalue = solve(s, leftpos, rightpos - 1, cnt + 1);
ret = Math.min(leftvalue, rightvalue);
break;
}
leftpos++;
rightpos--;
}
return ret;
}
static int stoi(String s) {
return Integer.valueOf(s);
}
}
// summuus에서 맞지 않는 부분이 나오면
// 왼쪽을 삭제하는 경우, 오른쪽을 삭제하는 경우 두가지
// 재귀사용, 한번 다른경우 또 다른 경우가 나오면 return 2를 한다.
// 두 문자가 다르면 재귀를 사용해서 반복문 break
'알고리즘 > 백준' 카테고리의 다른 글
[devmoon]백준 15566 - (Java)개구리1 (0) | 2021.07.13 |
---|---|
[devmoon]백준 2504 - (Java) 괄호의 값 (1) | 2021.07.10 |
[devmoon]백준 1062 골드4 - (Java) 가르침 (0) | 2021.07.06 |
[devmoon] 골드4 백준 - 2661 좋은 수열 (0) | 2021.07.05 |
[devmoon] 백준 1197 - (Java)최소 스패닝 트리 (0) | 2021.07.01 |