[백준] 17690 - 회문 (JAVA)

1. 소요시간 : 25분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 5
4. 문제 유형 : 문자열, 투포인터
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 문제 링크 : https://www.acmicpc.net/problem/17609
7. 푼 날짜 : 2023.05.12

1. 사용한 자료구조 & 알고리즘

문자열, 투포인터 알고리즘, 재귀..?

2. 사고과정

처음에 우선 재귀함수를 이용해서 문자열을 지운적이 없다면, 지우고 2갈래로 나눠서 탐색해야 겠다는 생각은 바로 들었고
투포인터 알고리즘을 써야겠다고 생각했다.

1. 그리고 문자열의 처음과 끝을 비교할 때 deque를 써야겠다고 생각하고 풀었음. -> 메모리 초과.
   👉 재귀에서 deque를 넘겨줄 때 덱이 무거워서 메모리 초과가 나는 것으로 예상.

2. 문자열로 재귀할 때 마다 시작 문자열, 끝 문자열을 비교하기 위해서 substring메소드로 문자열을 자르면서 재귀로 넘겨줌 -> 시간 초과.
   👉 단어의 길이가 100,000자니까 substring 할때마다 단어의 길이만큼의 시간복잡도가 요구되니, 시간초과가 날 것으로 예상.

3. 문자열을 자르지 말고, 문자열은 그대로 두되, start 와 end 변수를 추가해서 탐색하는 인덱스를 지정해주자!
   ✔️ 정답.

3. 풀이과정

1. 시작, 끝 인덱스를 지정해주고 재귀로 탐색. num의 시작 값은 2
2. 만약 end-start 가 0 미만이 된다면, 단어를 지운적이 없다면 num은 0.
3. 만약 단어를 지운 적이 있다면, num은 1이 된다. 그리고 return.
4. 단어의 시작 인덱스 값과 끝 인덱스 값이 같다면, start를 1늘리고, end를 1 줄여서 탐색한다.
5. 단어의 시작 인덱스 값과 끝 인덱스 값이 다른 경우에, 만약 지운 적이 없는 경우에만, 지운 것을 true로 처리하고, 시작 인덱스를 1 늘린 것과, 끝 인덱스를 1 줄인 것으로 나눠서 탐색한다.

4. 소스코드

import java.util.*;
import java.io.*;



public class Main{
	static int num = 2;

	public static void main(String[] args) throws IOException{

		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;


		int T = Integer.parseInt(br.readLine());

		while(T-->0 ) {
			num = 2;
			String word=br.readLine();	
		

			func(word,false,0,word.length()-1);

			System.out.println(num);

		}



	}
	public static void func(String word,boolean removed,int start,int end) {
		if(end-start<0) {
			
			if(removed==false) num = 0;
			else {
					num = 1;
			}
			
			return;

		}

		if(word.charAt(start)==word.charAt(end)) {
			func(word,removed,start+1,end-1);
		}
		
		else {
			if(removed==false) {
				func(word,true,start+1,end);
				func(word,true,start,end-1);
			}
			

		}



	}
}

5. 결과

6. 회고

문자열 문제가 오랜만이라 substring 시간복잡도를 까먹고 있었다..
주의해서 쓰자.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212