[자바] 백준 17609 - 회문 (java)

 문제 : boj17609

---

 

필요 알고리즘 개념

• 두 포인터 (투 포인터)
  
  • 회문이 아닐 시 예외처리가 들어가긴 하지만, 기본은 회문을 검사하는 투 포인터 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 기본적인 회문은 아래와 같이 찾을 수 있다. 양끝에서 두개의 포인터가 중간으로 오면서 두 포인터가 가르키는 값이 동일한지 확인하는 것이다.

 

  근데 이 문제는 1번은 건너띄어도 된다. 어떻게 처리하면 될까? summmmuus 를 탐색한다고 해보자. 탐색하다가 아래 위치에서 서로 다른 문자를 찾았다.

 

  이 경우 앞의 포인터를 한칸 더 가거나, 뒤의 포인터를 하나 더 간 후 계속 진행해주면 된다. 아래의 경우 두가지 분기 중 아래쪽껄로 진행하면 회문임을 찾을 수 있다. 어쨌든 한 번은 다른 문자가 나왔으니 '1'을 출력해주면 된다.

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<13);
    private static final StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int t = Integer.parseInt(br.readLine());
        while (t-->0)
            new Main().solution();
        System.out.print(sb);
    }

    private int palindrome(String str, int s, int e, int chk) {
        while (s < e) {
            if (str.charAt(s) == str.charAt(e)) {
                s++;
                e--;
                continue;
            }
            if (chk != 0)
                return 2;
            chk++;
            int res = palindrome(str, s, e-1, chk);
            if (res == 1) {
                e--;
                continue;
            }
            res = palindrome(str, s+1, e, chk);
            if (res == 1) {
                s++;
                continue;
            }
        }
        return chk;
    }

    public void solution() throws Exception {
        String str = br.readLine();
        sb.append(palindrome(str, 0, str.length()-1, 0)).append('\n');
    }
}