투 포인터 > 17609번

17609번

 

2개의 포인터가 각각 배열의 시작점과 끝점에 위치하여 반대로 이동하는 방법을 사용

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

public class baekjoon17609 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<n; i++) {
            String str = br.readLine();
            sb.append(twoPointer(str)+"\n");
        }
        System.out.println(sb);
    }
    public static int twoPointer (String str) {
        char [] arr = str.toCharArray();
        int count = 0;
        int start = 0;
        int end = arr.length-1;
        while(start<=end) {
            if(arr[start] == arr[end]) { // 양쪽 문자가 일치할 경우
                start++;
                end--;
            } else { // 다른 경우
                count = 1;
                int left = start+1; // 왼쪽 문자 무시 후 회문 여부 체크
                int right = end;

                while(left<=right) {
                    if(arr[left] == arr[right]) {
                        left++;
                        right--;
                    } else {
                        count++;
                        break;
                    }
                }
                left = start;
                right = end-1; // 오른쪽 문자 무시 후 회문 여부 체크
                while(left<=right) {
                    if(arr[left] == arr[right]) {
                        left++;
                        right--;
                    } else {
                        count++;
                        break;
                    }
                }
                if(count>=2) { // 왼쪽과 오른쪽 모두 다른 경우 > 3, 둘 중 하나만 다른 경우 > 2
                    return count-1;
                } else {
                    return count;
                }
            }
        }
        return count; // 회문이라면 0 반환
    }
}

 

코드가 지저분한 느낌이 들어 다른 방법도 찾아보았다

 

// 회문 여부를 체크하는 메서드와 유사 회문 여부를 체크하는 메서드 두 가지를 별도로 만든다

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

public class baekjoon17609_ {
    static char [] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            arr = br.readLine().toCharArray();
            int start = 0;
            int end = arr.length-1;
            if(checkP(start, end)) { // 회문인 경우
                sb.append(0+"\n");
                continue;
            }
            if(checkS(start, end)) {
                sb.append(1+"\n");
            } else {
                sb.append(2+"\n");
            }
        }
        System.out.println(sb);
    }

    public static boolean checkP(int start, int end) { // 회문 여부 체크
        while (start <= end) {
            if (arr[start] != (arr[end])) { // 두 포인터가 가리키는 문자가 달라지는 순간 false 반환
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    public static boolean checkS(int start, int end) { // 유사 회문 여부 체크
        while (start <= end) {
            if (arr[start]!=(arr[end])) { // 두 포인터가 가리키는 문자가 다른 경우
                boolean b1 = checkP(start + 1, end); // 왼쪽 문자 무시하고 나머지가 회문인지 체크
                boolean b2 = checkP(start, end - 1); // 오른쪽 문자 무시하고 나머지가 회문인지 체크
                if (b1 == false && b2 == false) {
                    return false; // 둘 다 회문이 될 수 없으면 유사 회문도 될 수 없음
                } else {
                    return true;
                }
            }
            start++;
            end--;
        }
        return true; // 회문인 경우 true 반환
    }
}

 

두 가지 풀이 모두 원리는 동일

 

양 끝에서 탐색을 시작

 

두 포인터가 가리키는 문자가 같은 경우 왼쪽 포인터는 오른쪽으로 한 칸 이동, 오른쪽 포인터는 왼쪽으로 한 칸 이동

 

두 포인터가 가리키는 문자가 달라지는 순간, 더 이상 회문은 될 수 없다

• 왼쪽 문자를 무시하고 다음 문자부터 끝 문자까지 회문인지 체크
• 오른쪽 문자를 무시하고 처음 문자부터 끝 문자 앞까지 회문인지 체크

 

둘 중 하나라도 만족할 경우 유사 회문이 될 수 있다