[백준] 17609번 회문 / C언어

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

 

백준 기준 난이도는 골드 5이며 생각하기에 유사회문에 대해 문제 해결 방식을 생각해 내면 그렇게 어렵지 않게 

알고리즘 보다는 구현 쪽으로 푸는 문제인거 같다.

 

 

# 문제 이해

 

팰린드롬은 문자열이 짝수면 인덱스 기준으로 맨 처음과 맨 끝이 같고 그렇게 맨 처음은 인덱스 +1 / 맨 끝은 인덱스 -1

이런식으로 하면 'abba' , 'baab' 와 같은 형식이 바로 팰린드롬이다.

 

홀수면 제일 중간 인덱스를 제외하고 나머지가 짝수처럼 앞 뒤가 같으면 팰린드롬이 된다.

 

자료구조를 배우면서 스택과 큐를 쓰면서 해본 기억이 있다. 

 

하지만 이 문제에는 또 다른 조건식인 유사회문이 있다.

 

유사회문이란 어떤 문자열에서 문자 하나를 지우게 되면 회문이 되는 것을 유사회문이라 한다.

 

 

# 문제 푼 방식

 

주어진 문자열이 유사 팰린드롬인지 아닌 확인하는 함수를 작성해 나갔다.

 

방식은 재귀함수를 통해 만들게 되었다.

 

유사 팰린드롬의 특성은? 하나만 빼면 팰린드롬이 되는 특성이다.

 

그래서 중간 인덱스 기준으로 왼쪽이던 오른쪽이던 하나를 빼고 다시 비교를 했을때 둘 중에 하나가 팰린드롬이 되면

 

그 문자열은 유사 팰린드롬이 되는 것을 알아야한다.

 

나머지는 간단하게 문자열을 기준으로 왼쪽 오른쪽 인덱스를 비교하여 팰린드롬인지 아닌지를 판단하는 함수를 짜주면 된다.

 

가장 중요한 것은 유사 팰린드롬을 어떻게 판단하고 만들 것인지가 중요했다.

 

 

bool pseudo(const char* string, int left, int right) {
    while (left <= right) {
        if (string[left] == string[right]) {
            left++;
            right--;
        }
        else {
            return false;
        }
    }
    return true;
}

 

위의 코드는 유사 팰린드롬을 확인하는 재귀형식 코드를 짜놓은 것이다.

 

bool 형식을 통해서 왼쪽 flag 나 오른쪽 flag의 인덱스 한 개를 제외 시키고 다시 팰린드롬을 확인하여 유사인지를 

 

판별하는 형식으로 짜게 되었다.

 while (left <= right) {
        if (string[left] != string[right]) {
     
            bool left_flag = pseudo(string, left + 1, right);
            bool right_flag = pseudo(string, left, right - 1);
            if (left_flag || right_flag) {
                return 1;  
            }
            else {
                return 2;
            }

 

그렇게 위의 코드를 보면 유사인지 아닌지 판별을 하면 된다.

 

 

 

# 전체 코드

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool pseudo(const char* string, int left, int right) {
    while (left <= right) {
        if (string[left] == string[right]) {
            left++;
            right--;
        }
        else {
            return false;
        }
    }
    return true;
}

int is_palindrom(const char* string) {
    int len = strlen(string);
    int left = 0;
    int right = len - 1;

    while (left <= right) {
        if (string[left] != string[right]) {
       
            bool left_flag = pseudo(string, left + 1, right);
            bool right_flag = pseudo(string, left, right - 1);
            if (left_flag || right_flag) {
                return 1; 
            }
            else {
                return 2;  
            }
        }
        left++;
        right--;
    }
    return 0; 
}

int main() {
    int cases;
    scanf_s("%d", &cases);

    for (int i = 0; i < cases; i++) {
        char string[100001]; 
        scanf_s("%s", string);
        printf("%d\n", is_palindrom(string));
    }

    return 0;
}