[백준 JAVA] 17609 회문

문제

---

https://www.acmicpc.net/problem/17609

17609번: 회문

 

풀이방법

---

 

처음에 입력받은 문자열이 회문이라면, 회문인지 판별할 필요없이 0을 출력한다.

 

처음에 입력받은 문자열이 회문이 아니라면, 알고리즘을 진행한다.

 

모든 글자들을 다 확인할 필요 없이, 회문이 아니게 된 문자를 앞, 뒤를 각각 지워보고 회문인지 판별한 뒤에, 회문이라면 1을, 회문이 아니라면 2를 출력하면된다. 그 이상의 글자들을 다 확인해봤자, 처음 회문이 아닌 문자열은 회문이 아니기 때문이다. 이 생각을 하지않고 문자열을 처음부터 끝까지 다 비교하면 시간초과가 발생한다.

 

회문이 아니라면, remove(i,list.size()-i-1); 로 지울 위치를 remove함수의 인자로 넘겨준다.

 

문자열을 지우기에 StringBuilder가 쓰기 편해서 StringBuilder의 deleteCharAt함수를 사용해서 문자를 지우고, 다시 list에 add해주는 과정을 거쳤다.

 

회문인지 아닌지 판단하기 위해서 check라는 함수를 우선 만들었다.

list의 처음과 끝을 비교해가며, 달라지는 값이 있으면 false를 return 하고, 모든 값이 같으면(회문이라면) true를 return 한다.

 

static boolean check() {
	for(int i=0; i<=list.size()/2; i++) {
		if(list.get(i)!=list.get(list.size()-i-1)) {
			return false;
			}
		}
	return true;
	}

 

코드는 아래와 같다.

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
	
	static String st;
	static char put;
	static ArrayList<Character> list;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine());
		int T=Integer.parseInt(str.nextToken());
		for(int t=0; t<T; t++) {
			st=br.readLine();
			
			list = new ArrayList<Character>();
			
			for(int i=0; i<st.length(); i++) {
				list.add(st.charAt(i)); //한글자씩 들어있는 문자 배열 list 만들기
			}
			
			
			for(int i=0; i<=list.size()/2; i++) {
				if(list.get(i)!=list.get(list.size()-i-1)) {
					remove(i,list.size()-i-1); //회문이 아니자마자 remove함수로 가기
					break;
					}
				if(i==list.size()/2) {
					System.out.println("0");
					}
				}

			
	
		}
	
		
	}

static boolean check() {
	for(int i=0; i<=list.size()/2; i++) {
		if(list.get(i)!=list.get(list.size()-i-1)) {
			return false;
			}
		}
	return true;
	}

static void remove(int position,int position2) {
	StringBuilder origin = new StringBuilder(st); //StringBuilder로 만든 후 

	StringBuilder check1 = origin;
	check1 = check1.deleteCharAt(position); //position의 문자열 지우기
	String s1= check1.toString(); 

	
	list = new ArrayList<Character>();
	for(int i=0; i<s1.length(); i++) {
		list.add(s1.charAt(i)); //다시 리스트에 문자열 넣기
	}

	if(check()==true) {
		System.out.println(1); //회문인지 확인해보고 회문이라면 1을 출력
	}
	else {
		
		
		origin = new StringBuilder(st);
		StringBuilder check2 = origin;
		check2 = check2.deleteCharAt(position2);//position2의 문자열 지우기
		
		s1= check2.toString();

		list = new ArrayList<Character>();
		for(int i=0; i<s1.length(); i++) {
			list.add(s1.charAt(i));//다시 리스트에 문자열 넣기
		}

		if(check()==true) {
			System.out.println("1");//회문인지 확인해보고 회문이라면 1을 출력
			return;
		}
		else {
			System.out.println("2");//회문인지 확인해보고 회문이 아니라면 2를 출력
			return;
		}
		
	}

	}
}