[백준 1254] 팰린드롬 만들기 - Python

문제 보기

[사용한 알고리즘]

브루트 포스, 구현, 부분 집합

 

[접근 방식]

입력받은 문자열 S가 팰린드롬인지 확인합니다. 만약 팰린드롬이 아니라면 입력 문자열 S를 뒤집어서 부분 팰린드롬의 길이를 찾은 후 최종 팰린드롬의 길이를 출력합니다. 이 과정은 아래 알고리즘에서 자세히 설명하도록 하겠습니다.

 

[알고리즘]

1. 문자열 S가 팰린드롬인지 확인합니다. 만약 팰린드롬이라면 문자열 S의 길이를 출력합니다.

2. 문자열 S가 팰린드롬이 아니라면 reversed(S)에서 인덱스 0부터 시작하는 부분 팰린드롬의 문자열의 길이를 구합니다.

3. 문자열(S)의 길이 * 2 - 부분 팰린드롬 문자열의 길이를 출력합니다.

 

abab를 예로 들어 설명하겠습니다.

1. abab가 팰린드롬인지 확인합니다. 팰린드롬이 아니므로 2번 과정을 수행합니다.
2. reversed(S)를 구합니다. -> baba
3. baba에서 인덱스 0 [b]부터 시작하는 부분 팰린드롬을 구합니다. -> baba
4. 부분 팰린드롬의 문자열이 "b"이므로 부분 문자열의 길이는 1입니다.
5. 따라서 문자열(S)의 길이 * 2 - 부분 팰린드롬 문자열의 길이(4 * 2 - 1)는 7입니다.

원래 문자열과 역순의 문자열이 겹치는 최대 길이를 찾는다고 생각하면 됩니다.

 

[코드]

def is_pallindrome(str):
    reversed_str = list(reversed(str))
    for i in range(len(str)):
        if str[i] == reversed_str[i]:
            continue
        else:
            return False
    return True


if __name__ == "__main__":
    s = input()
    if is_pallindrome(s):  # 팰린드롬
        print(len(s))
    else:
        reversed_str = list(reversed(s))
        for i in range(len(s) - 1, 0, -1):
            if is_pallindrome(reversed_str[:i]):
                print(len(s) * 2 - i)
                break
            elif i == 1:
                print(len(s) * 2)