[백준/python]1254번 팰린드롬 만들기 - string

python 문자열

문자열 거꾸로 출력하기

반복문을 통해 새로운 문자열을 만드는 방법 외에 ‘pythonic’한 방법을 알아보자.

1. .reverse() 함수 이용하기 - 문자열을 리스트로 변환하고 reverse함수를 이용하여 순서를 뒤집는 방법
2. s[::-1] - 문자열 s를 [::-1]이라는 인덱스를 이용하여 호출하면 거꾸로 뒤집힌 문자열이 반환된다.

1254번 풀이

처음 생각한 풀이

주어진 문자열에 팰린드롬이 있더라도 마지막 문자가 포함되지 않으면 의미가 없다.

예를 들어 xabcbayz 라는 문자열이 있다면 abcba는 팰린드롬이다. 하지만 x와 y,z가 있기 때문에 오른쪽에 새로운 문자열을 추가하더라도 팰린드롬을 만들 수 없다.

1. 문자열이 팰린드롬인 두 가지 경우가 있다. abcba와 같이 중간에 하나의 문자가 있는 경우와 abba와 같이 좌우 대칭인 경우가 있다.
2. 문자열의 길이만큼 반복문을 실행하며 현재 인덱스의 문자를 기준으로 팰린드롬인지, 팰린드롬이라면 문자열의 끝까지 이어지는 지 체크한다.
3. 문자열의 끝까지 팰린드롬인 경우 가장 긴 팰린드롬을 갱신한다.
4. 문자열 자체가 팰린드롬인 경우가 아니라면 (전체 문자열의 길이 - 팰린드롬의 길이) 만큼 새로운 문자열을 추가해주면 된다.

코드

#팰린드롬 만들기
s = input()
length=len(s)

max_length = 0
for i in range(1,length):
    if s[i]==s[i-1]:
        
        lengthToEnd = length-1-i
        if lengthToEnd==0:
            max_length= max(max_length,2)
            
        else:
            startIdx = i-1-(lengthToEnd)
            if startIdx >=0 :
                if s[startIdx:i] == s[length-1:i-1:-1] :
                    max_length = max(max_length,2*(lengthToEnd+1))
                
    if i>=2 and s[i]==s[i-2] :
        
        lengthToEnd= length-1-i
        
        if lengthToEnd ==0:
            max_length = max(max_length,3)
            
        else:
            startIdx = i-2 -(lengthToEnd)
            if startIdx>=0:
                if s[startIdx:i-1] == s[length-1:i-1:-1] :
                    max_length = max(max_length, 2*(lengthToEnd+1)+1)
    

if max_length==length:
    print(length)
elif max_length>=1:
    print(2*(length-max_length)+max_length)
else:
    print(2*length -1)

새로운 풀이

처음 문제를 보고 구현에 초점을 두고 문제를 풀었고 백준 기준으로 가장 빠른 시간으로 통과했기 때문에 나름 괜찮은 풀이라고 생각했다. 문자열이라는 점과 파이썬의 문법을 이용하여 간단하게 풀 수 있었다.

풀이

1. 문자열의 길이만큼 반복문을 실행하며 i번째 인덱스로 시작하는 문자열과 이를 거꾸로한 문자열을 비교한다.
2. 두 문자열이 같다면 i번째 문자열 앞에 있는 문자열의 길이만큼 새로 추가해주면 팰린드롬을 만들 수 있다.

해답을 보고 나면 쉽게 이해할 수 있지만 해당 풀이를 떠올리기가 쉽지 않았다.

코드

s=input()
length=len(s)

for i in range(lenght):
	if s[i:] == s[i:][::-1] :
		print(length + i)
		break