백준 17609 - 회문

백준 17609 - 회문

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

감을 못잡아서 다른 사람 풀이를 봤다. OMG! 너무나 깔끔하다..

★ 풀이

문자열이 회문인지는 투포인터를 통해서 시간을 단축을 하며 구할 수 있다.

이 문제의 포인트는 문자열이 유사 회문인지 아닌지를 구할 수 있는 가이다.

우선 함수로 구성해봤고, 전체적인 동작은 아래와 같다.

한가지 기억해야 할 것은 유사 회문의 경우 문자 1개를 없애서 대칭을 만들 수 있는 문자열이라는 것이다. 따라서 While문을 통해서 대칭을 이루지 않는 노란색 부분 이후에는 더 이상 문자를 제거할 수 없다. 즉 왼쪽이나 오른쪽 문자 둘 중 하나만 없애서 대칭을 만들 수 있어야 유사 회문이 성립할 수 있다는 말이다.

회문을 구하는 함수는 앞서 만들어 놓았으므로 이용해서 구하면 쉽게 구할 수 있다. 아마 다른 풀이 또한 비슷한 원리를 통해 구하겠지만 확실히 함수를 이용해서 구하는게 읽기도 편하고, 함수를 재활용 할 수도 있고.. 여러가지 면에서 편한 것 같다.

★ 소스 코드

import java.io.*; import java.util.*; // 좋은 코드 흡수하기! public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static String s; public static void main(String[] args) throws IOException { // 회문 : 0 // 유사회문 : 1(제한 1개) // 나머지 : 2 int n = Integer.parseInt(br.readLine()); while (n-- > 0) { s = br.readLine(); int left = 0; int right = s.length() - 1; if(isPalin(left, right)) { bw.write(0+"

"); }else if(isAlmostPalin(left, right)) { bw.write(1+"

"); }else { bw.write(2+"

"); } } bw.flush(); } static boolean isPalin(int left, int right) { while(left <= right) { if(s.charAt(left) == s.charAt(right)) { left++; right--; }else { return false; } } return true; } static boolean isAlmostPalin(int left, int right) { while(left <= right) { if(s.charAt(left) != s.charAt(right)) { boolean a = isPalin(left + 1, right); boolean b = isPalin(left, right - 1); if(a == false && b == false) { return false; }else return true; } left++; right--; } return true; } }

from http://sweet-smell.tistory.com/104 by ccl(A) rewrite - 2021-11-20 03:29:02