[구현/문자열] 백준 1254 팰린드롭 만들기 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1254번: 팰린드롬 만들기

 

 

 

2. 문제 풀이

 팰린드롬을 만들기 위해서 추가하는 문자의 최소 개수를 구하는 문제입니다.

 

2022.02.06 - [Algorithm] - [구현/수학] 백준 10988 팰린드롬인지 확인하기 - Python

[구현/수학] 백준 10988 팰린드롬인지 확인하기 - Python

 문자열 슬라이싱을 이용해서 회문인지 쉽게 판별할 수 있습니다.

 

 

 

3. 코드

S = input()
start = 0
end = len(S)-1
res = 0 #앞뒤가 다른 문자 수
while start < end:
    #앞뒤가 다르면 res+1
    if S[start] != S[end]:
        res += 1
        start += 1
    #앞뒤가 같으면 같이 이동
    else:
        start += 1
        end -= 1
print(len(S) + res)

 슬라이싱을 사용하지 않고 풀어보려 했으나, aaba와 같은 경우는 로직이 꼬이더군요.

 

 

S = input()
for i in range(len(S)):
    if S[i:] == S[i:][::-1]:
        print(len(S)+i)
        break

 앞에서부터 하나씩 줄여가며 회문인지 확인하는 게 쉽습니다. 회문이 되지 않는 앞 글자만큼만 뒤에 붙여주면 회문이 완성됩니다.

 예를 들어, aaba는 aabaa가 최선입니다.

1) aaba ≠ abaa

2) aba = aba (회문)

따라서 1번에서 뺀 a만 뒤에 붙여주면 회문입니다. aabaa