[백준] 17609번 회문 JAVA (자바) 풀이

문제 17609번 (투포인터)

 :  회문이란? 앞뒤로 같은 순서의 문자로 구성된 문자열 
    (예) 'abba’, ‘kayak’, ‘reviver’, ‘madam’

 :  유사회문이란? 한 문자를 삭제해서 회문으로 만들 수 있는 문자열
    (예) 'summuus’ 에서 5 or 6 번째 문자 제거하면 회문이 된다

 

 :  회문이면 0, 유사회문이면 1, 그 외는 2를 출력한다

 

[입력]

 :  첫 줄에 문자열 개수 T

    둘째 줄부터 T개의 줄에 문자열 하나씩 입력 ( 3 ≤ 문자열 길이 ≤100,000 )
   (문자열 길이는 3영문 알파벳 소문자로 이루어져있다)

 

 

[출력]

 :  회문이면 0, 유사회문이면 1, 그 외는 2를 출력

 

 [설명]

 

출차 https://nahwasa.com/

 

1. 양 끝에서부터 검사하기 시작한다
   → 이때 시작지점, 끝지점 두 개의 포인터 필요
   
   
2.  시작 = 끝 이라면 정확히 대칭이다
   → 다음 지점으로 넘어가기 start ++ ~ end --
   → 시작지점은 앞으로 가고 끝지점은 뒤로 가면서 좁혀진다 
   
3.  시작 ≠ 끝 이라면 대칭이 아니다 ( 유사회문? or 일반 문자열? 확인필요!! )
   → 왼쪽 문자 없애보고 오른쪽 문자 없애보면서 유사회문 또는 일반 문자열 확인한다
   → 확인 방법
       1. 다시 한 번(재귀) 현재 지점의 문자열만 투포인터에 넣어보고 대칭이라면 유사회문
       2. 다시 한 번(재귀) 현재 지점의 문자열만 투포인터에 넣어보고 대칭이 아니라면 일반 문자열
   
   

 [코드]

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());

        String[] arr = new String[T];
        for (int i = 0; i < T; i++) {
            arr[i] = br.readLine();
        }

        for (int i = 0; i < T; i++) {
            String current = arr[i];
            System.out.println(point(0, current.length() - 1, current, 0));
        }
    }

    private static int point(int start, int end, String s1, int check) {
    
        if(check >=2) return 2;

        while (start < end) { 
            if (s1.charAt(start) == s1.charAt(end)) {
                start++;
                end--;
            } else {
                return Math.min(point(s + 1, e, s1, check + 1), point(s, e - 1, s1, check + 1));
            }
        }
        return check;
    }
}

 

 

 [해설]
     

 :  int T = Integer.parseInt(br.readLine()); 첫째줄 입력

 :  String[] arr = new String[T];  문자열 배열
    for (int i = 0; i < T; i++) {
          arr[i] = br.readLine();  T개 줄의 입력받기
    }

    for (int i = 0; i < T; i++) {
           String current = arr[i];  배열 current에 저장
           System.out.println(point(0, current.length() - 1, current, 0)); 0부터 시작해서 current 길이 -1 만큼 반복
    }
    

 :  private static int point(int s, int e, String s1, int check) {
        
        if(check >=2) return 2;  아래 else에서 check 2 이상이면 2 그대로 출력

        while (s < e) {
            if (s1.charAt(s) == s1.charAt(e)) { 양 끝을 검사해서 문자 일치한다면( = 완벽히 대칭되는 알파벳 )
                s++;  시작지점 갱신 ++                 대칭일 때에는 check를 카운트 하지 않는다 (회문은 0 이므로)
                e--;  끝지점 갱신 --                       
            }

 

            else {  양 끝 문자가 일치하지 않을 경우 (유사회문? or 일반 문자열? 확인해보기)
                return Math.min(point(s + 1, e, s1, check + 1), point(s, e - 1, s1, check + 1));
                끝지점은 그대로 두고 시작지점 좁혔을 때 / 시작지점 그대로 두고 끝지점 좁혔을 때
                회문이면 check = 0  /  그 외의 것들은 +1
                check + 1 씩 하면 1 or 2 이 중에 작은 것을 출력 !
            }  즉 최종 check가 1이 된다면 유사회문인 것이다
        }
        return check;  체크된 횟수 출력
    }
}

 

 

 

 

 

이제 풀어보러 갈께요 :)

 

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

17609번: 회문

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *