[백준] 17609 회문 - JAVA

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

17609번: 회문

 

 

[알고리즘]

• 투 포인터
• 제일 앞/뒤 양끝에서 두개의 포인터가 중간으로 오면서 투 포인터가 가리키는 값이 동일한지 확인 
• 만약 다른 값이 나온다면 하나씩 제외하고 회문인지 확인하여 회문/유사회문/일반 판별 

---

 

[설계]

• 양 끝을 가리키는 포인터로 시작 (left /right) 
• 만약 left, right 가 가리키는 값이 같을 경우 left와 right를 가운데쪽으로 이동
• left, right가 가리키는 값이 다를 경우 
  1. left가 가리키는 문자를 제외하고 회문인지 확인 
  2. right가 가리키는 문자를 제외하고 회문인지 확인
  3. 둘 중 하나라도 회문이라면 "유사회문", 그렇지 않다면 "일반 문자열"

💡예를 들어, xyyyyxy 라는 문자열이 입력으로 주어졌다고 가정해보자. left ='x' , right='y'로 투 포인터가 가리키는 값이 다르다. 
   1. left 가 가리키는 문자를 제외하고 yyyyxy 가 회문인지 확인 >회문 아님 
   2. right 가 가리키는 문자를 제외하고 xyyyyx 가 회문인지 확인 > 회문
즉, "유사회문" 

 

 

[구현 과정]

 

1. check() : 주어진 문자열을 투 포인터로 탐색하며 회문인지 확인하는 함수

- 처음 투포인터는 양 끝 (left / right) 으로 하여 시작한다. 
- left < right 일 동안 아래 과정을 반복한다. (같거나 left 가 커지면 종료) 
- 투 포인터가 가리키는 값이 같을 경우 : 다음 문자를 탐색하기 위해 중간으로 모인다. (left ++, right--) 
- 투 포인터가 가리키는 값이 다를 경우 : 유사회문인지 확인
   1. left가 가리키는 문자를 제외하고 회문인지 확인. checkSec (left+1, right)
   2. right가 가리키는 문자를 제외하고 회문인지 확인. checkSec (left, right-1)  
- (1,2) 중 하나라도 회문이 존재한다면 해당 문자열은 "유사회문" 이므로 1 반환 
- 그렇지 않다면 "일반문자열" 2 반환 
- while 문이 무사히 종료되었다면 "회문" 0 반환 

 

2. checkSec() : check() 함수에서 문자를 하나씩 제외한 (서브)문자열이 회문인지 확인 (투 포인터 로직은 동일)

- 양 끝을 투 포인터로 하여 가리키는 값이 동일한지 확인 
- left < right 일 동안 아래 과정을 반복한다. (같거나 left 가 커지면 종료) 
- 투 포인터가 가리키는 값이 같을 경우 : 다음 문자를 탐색하기 위해 중간으로 모인다. (left ++, right--) 
- 투 포인터가 가리키는 값이 다를 경우 : 회문이 아니므로 false 반환 
- while 문이 무사히 종료되었다면 true 반환 (=회문) 

 

---

 

[소스 코드]

import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		int T= Integer.parseInt(br.readLine()); 
		while(T-- >0) {
			String s= br.readLine(); 
			int res= check(s, 0, s.length()-1); 
			System.out.println(res);
		}
		
	}//end of main
	
	/*
	 * 0:화문 
	 * 1:유사화문
	 * 2:그 외/
	 */
	private static int check(String s, int left, int right) {
		while(left<right) {
			
			if(s.charAt(left)==s.charAt(right)) {
				left++;
				right--; 
			}
			
			//만약 다를 경우 ,
			else {
				//왼쪽 하나 제외/ 오른쪽 하나 제외하고 회문인지 확인 
				boolean res1 = checkSec(s, left+1, right);
				boolean res2 = checkSec(s, left, right-1); 
                
				//둘중 하나라도 회문이라면, 유사회문
				if(res1 || res2) return 1;
				
				return 2;
			}
		}
		return 0;
	}
    
	private static boolean checkSec (String s, int left, int right) {
		while(left< right) {
			if(s.charAt(left) == s.charAt(right)) {
				left++;
				right--; 
				continue; 
			}
			return false; 
		}
		return true; 
	}
}//end of class