[백준/Python, Java] 17609 회문

 

📌문제 탐색하기

• 유사회문 : 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열
• 제시된 문자열이 그 자체로 회문인지, 유사회문인지, 둘 다 아닌 일반 문자열인지 판단하는 프로그램 작성하기

입력

• 문자열의 개수 T (1 ≤ T ≤ 30)
• T개의 줄에 걸쳐 한 줄에 하나의 문자열 (3 ≤ 문자열 길이 ≤ 100,000, 영문 알파벳 소문자로만 이루어짐)

출력

• 각 문자열이 회문이면 0, 유사 회문이면 1, 모두 아니면 2를 한 줄에 하나씩 출력

풀이 방법 생각해보기

투포인터 알고리즘을 사용해서 두 개의 포인터가 첫 글자와 마지막 글자를 가리키도록 하고, 각 포인터를 한칸씩 이동시키면서 현재 가리키고 있는 글자가 같은지 확인한다. 두 개의 포인터가 만날 때까지 서로 가리키고 있는 글자가 같다면 회문으로 판단할 수 있다. 만약 두 포인터가 가리키는 글자가 다르다면, 둘 중 하나의 문자를 제거하고 회문 여부를 판별해서 유사회문을 판단해낼 수 있다.

주어진 문자열의 개수만큼 각 문자열에 대해 회문 여부를 판별해야 하므로 O(30) * O(100,000) = O(3,000,000)으로 시간 내에 풀이가 가능하다.

 

 

📌코드 설계하기

1. 문자열이 주어지면 회문을 판별할 함수 is_palindrome(str, p1, p2, is_pseudo)을 정의한다.
   
   1. p1이 p2보다 작을 때 동안 아래 과정을 반복한다.
   2. str[p1]과 str[p2]를 비교하여 같다면 p1에 1을 더하고, p2에 1을 뺀다.
   3. 만약 str[p1], str[p2]가 다르다면, is_pseudo가 True인 경우 2을 반환하고, is_pseudo가 False라면 is_palindrome(str, p1+1, p2, True), is_palindrome(str, p1, p2-1, True)를 호출해 둘 중 하나가 0이라면 1을 둘 다 2라면 2를 반환한다.
   4. p1이 p2보다 같거나 커진 경우, 0을 반환한다. 
2. 문자열의 개수를 저장할 변수 T를 생성하고, 문자열 개수를 입력받는다.
3. T만큼 반복하면서, 문자열 str을 입력받고 is_palindrome(str, 0, len(str)-1, False)을 호출해서 문자열의 종류를 판별한 결과를 반환받는다.
4. 3에서 반환된 결과를 한 줄씩 출력한다.

 

📌 정답 코드

Python

import sys
input = sys.stdin.readline

def is_palindrome(str, p1, p2, is_pseudo):
    while p1 < p2:
        if str[p1] == str[p2]:
            p1 += 1
            p2 -= 1
        else:
            if is_pseudo: return 2
            return 2 if is_palindrome(str, p1+1, p2, True) and is_palindrome(str, p1, p2-1, True) else 1
    return 0

for _ in range(int(input())):
    str = input().strip()
    print(is_palindrome(str, 0, len(str)-1, False))

 

Java

import java.io.*;

public class Main {
    public static int is_palindrome(String str, int p1, int p2, boolean is_pseudo) {
        while (p1 < p2) {
            if (str.charAt(p1) == str.charAt(p2)) {
                p1++;
                p2--;
            } else {
                if (is_pseudo) return 2;
                if (is_palindrome(str, p1, p2-1, true) == 0 || is_palindrome(str, p1+1, p2, true) == 0) return 1;
                return 2;
            }
        }
        return 0;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            String str = br.readLine();
            System.out.println(is_palindrome(str, 0, str.length()-1, false));
        }
    }
}

 

시간 복잡도

각 문자마다 한 번씩 is_palindrome을 통해 회문 검사를 한다. 회문 검사의 경우, 문자열의 양 끝에서 중앙으로 이동하면서 비교하는 데 O(n)의 시간복잡도가 소요된다. 문자가 다를 경우 최대 2개의 재귀 호출을 수행하지만, is_pseudo 조건문에 의해 최대 한 번 깊이의 재귀 호출이 일어나므로, 최악의 경우에도 O(n)으로 동작한다.

 

공간 복잡도

재귀 호출에 따른 스택 사용이 주요 공간 사용인데, 재귀 깊이가 최대 2(최초 호출 + 최대 1번의 재귀 호출)이고, 각 재귀 호출에서는 상수 개의 변수만 사용하므로 공간 복잡도는 O(1)이다.