[Algorithm] 백준 문자열 문제 - 회문(17609) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 문자열 문제 회문 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/17609

17609번: 회문

 

1. 풀이 소스

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        List<String> strs = new ArrayList<>(); // 문자열 담을 리스트

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) strs.add(br.readLine()); // 문자열 리스트에 추가

        for (String str : strs) {
            int cnt = 0; // 회문, 유사회문, 그 외 판단
            int left = 0; // 포인터 왼쪽
            int right = str.length() - 1; // 포인터 오른쪽

            while (left < right) { // left 포인터가 right 포인터보다 작을 때 까지 , 만약 홀수길이이의 문자열이라면 중앙을 제외한 나머지가 모두 맞으면 가능 abkba

            if (str.charAt(left) != str.charAt(right)) { // 만약 양쪽 포인터가 가리키는 문자열이 같지 않다면
                    if (str.charAt(left + 1) == str.charAt(right)) { // 만약 두 포인터가 같지 않다면 유사회문 판단을 위해 left를 한칸 옮겨서 판단 
                        cnt = move(str, left + 1, right);
                        if (cnt == 1) break; // 만약 왼쪽 포인터를 한번 더 옮긴 것이 유사회문이라면 종료 
                    }
                    if (str.charAt(left) == str.charAt(right - 1)) { // 유사회문이 아닌 경우 right를 한칸 옮기고 진행 
                        cnt = move(str, left, right - 1);
                        if (cnt == 1) break; // 유사회문 종료 
                    }
                    cnt = 2; // 둘 다 아니거나, cnt = 2라면, 
                    break;
                } else { // 유사회문 없이 돌아간다면, 하나씩 포인터 양쪽에서 옮겨주기 
                    left++;
                    right--;
                }
            }

            if (cnt == 0) sb.append(0).append("\n");
            else if (cnt == 1) sb.append(1).append("\n");
            else sb.append(2).append("\n");
        }

        System.out.print(sb);
    }

    static int move(String str, int left, int right) { // 유사회문 판단을 위한 포인터 이동 
        while (left < right) {
            if (str.charAt(left) == str.charAt(right)) {
                left++;
                right--;
            } else return 2; // 유사회문도 아니므로 2 리턴 
        }
        return 1; // 유사회문 
    }
}

 

2. 풀이 중점 사항 

 

이번 풀이는 포인터를 이동하는 방식으로 문제를 해결할 수 있었습니다. 

 

    a      b       c         b        a  

   p1 ->                          <- p2

 

포인터를 하나씩 옮겨가며 값을 찾되, 두 포인터가 가리키는 값이 다를 수 있습니다. 이 경우 유사회문일 가능성이 있으므로, left를 옮기고 검사하고, 아니라면, 오른쪽을 한번 더 옮겨서 유사회문을 검사하는 로직을 작성하였습니다.

 

 

if (str.charAt(left + 1) == str.charAt(right)) { // 만약 두 포인터가 같지 않다면 유사회문 판단을 위해 left를 한칸 옮겨서 판단
    cnt = move(str, left + 1, right);
    if (cnt == 1) break; // 만약 왼쪽 포인터를 한번 더 옮긴 것이 유사회문이라면 종료
}
if (str.charAt(left) == str.charAt(right - 1)) { // 유사회문이 아닌 경우 right를 한칸 옮기고 진행
    cnt = move(str, left, right - 1);
    if (cnt == 1) break; // 유사회문 종료
}
cnt = 2; // 둘 다 아니거나, cnt = 2라면,
break;

 

다음과 같이, if - else if 가 아니라 왼쪽 유사회문 검사 후, 오른쪽 유사회문 검사하는 이유는 반례에서 찾을 수 있습니다.

만약 테스트 케이스가 'abbab'가 주어졌다고 가정하겠습니다. 

 

// 잘못된 코드

if (str.charAt(left + 1) == str.charAt(right)) { // 만약 두 포인터가 같지 않다면 유사회문 판단을 위해 left를 한칸 옮겨서 판단
    cnt = move(str, left + 1, right);
    if (cnt == 1) break; // 만약 왼쪽 포인터를 한번 더 옮긴 것이 유사회문이라면 종료
}
else if (str.charAt(left) == str.charAt(right - 1)) { // 유사회문이 아닌 경우 right를 한칸 옮기고 진행
    cnt = move(str, left, right - 1);
    if (cnt == 1) break; // 유사회문 종료
}
cnt = 2; // 둘 다 아니거나, cnt = 2라면,
break;

 

만약 이처럼 if else if를 적용하게 된다면, 먼저 기술된 left + 1만 실행됩니다.

 

a            b                 b             a             b

p1                                                          p2       -------> arr[p1] != arr[p2]

             p1                                             p2       -------> arr[p1] = arr[p2]

                              p1           p2                        -------> arr[1]  != arr[p2]

 

abbab 는 유사회문일지라도 left + 1를 하면 일반 문자열이 됩니다.

따라서, if문으로 left + 1을 먼저 거치고, 오른쪽도 right - 1로 검사할 수 있도록 하였습니다.

 

a            b                 b             a             b

p1                                                          p2       -------> arr[p1] != arr[p2]

p1                                           p2                      -------> arr[p1] = arr[p2]

              p1               p2                                    -------> arr[1]  = arr[p2] 

 

 

right - 1도 적용하면 다음처럼 유사회문을 찾을 수 있습니다.

이상으로 회문 자바 풀이를 마치도록 하겠습니다.! 감사합니다.!