[백준BOJ] 7609번 회문.java

 

백준 저지에서 회문을 자바를 통해 풀어 보았다. 

 

7609번 회문.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

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

17609번: 회문

17609번 회문 

문제

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.
여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다. 

설명

투포인터를 통해 풀 수 있다.

 

투포인터는 회문인지 확인하기 위해 구한다. 문자열의 시작과 끝을 가리키는 index인 start와 end를 생성한다. start가 end보다 작은 동안 반복문을 돌린다. start와 end에 존재하는 문자가 같다면 start는 1증가, end는 1감소시킨다. 만약 start와 end가 같거나 start가 end보다 커질 때까지 반복된다면 문자열은 회문이다. 이때는 0을 출력한다.

 

만약 start와 end가 달라지는 지점이 있다면 start에 위치한 문자 혹은 end에 위치한 문자를 제외하고 남은 문자열이 회문인지 확인해야한다. 즉 현재 start부터 end-1까지의 문자열, 혹은 start+1부터 end까지의 문자열이 회문이라면 유사회문이므로 1을 출력한다.

 

그 외의 경우는 회문도, 유사회문도 아니다. 따라서 2를 출력한다.  

코드

//17609번 회문.java
package boj20220114;

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

public class 회문_17609 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws NumberFormatException, IOException {
		int T = Integer.parseInt(br.readLine());
		for(int t=0;t<T;t++) {
			String str = br.readLine();
			int head=0;
			int tail=str.length()-1;
			int answer=0;
			while(head<tail) {
				//System.out.println(head+" "+tail+":"+answer);
				if(str.charAt(head)==str.charAt(tail)) {
					head++;
					tail--;
				}
				else if(isPalindrome(str.substring(head+1,tail+1))) {
					answer = 1;
					break;
				}
				else if(isPalindrome(str.substring(head,tail))) {
					answer = 1;
					break;
				}
				else {
					answer=2;
					break;
				}
				
			}
			sb.append(answer+"\n");
		}
		System.out.println(sb.toString());
	}
    static public boolean isPalindrome(String str) {
    	int head =0;
    	int tail =str.length()-1;
    	
    	while(head<tail) {
    		if(str.charAt(head)==str.charAt(tail)) {
				head++;
				tail--;
			}
    		else return false;
    	}
    	return true;
    }
}