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

Table of Contents

• 문제
• 예제
• 계획
• 풀이
  • 오답
  • 첫 번째 정답
  • 두 번째 정답

문제

• 백준 1254 팰린드롬 만들기

주어진 단어의 뒤에 0개 이상의 문자를 추가해 만들어지는 팰린드롬 단어의 최소 길이를 구하라.

예제

입력 → 출력

1. abab → 5
2. abacaba → 7
3. qwerty → 11
4. abdfhdyrbdbsdfghjkllkjhgfds → 38

계획

처음엔 1213 팰린드롬 만들기 문제랑 같은 논리인 줄 알고 잠깐 시간을 날렸었다.

문제를 제대로 이해하고 나서는 투 포인터 탐색으로 양 끝에서부터 글자를 비교하면서 서로 다르면 뒤에 글자를 추가한다는 전제로 포인터를 계속 진행시켜서 최종 개수를 세도록 했는데 틀렸고, 반례도 찾았다.

그 후로 투 포인터 탐색으로는 아무리 고민을 해도 답이 안 나오는 것 같아서 어떤 알고리즘을 써야 풀리는지 봤는데 브루트포스라고 해서 금방 해결했다.

풀이

36분 42초에서 힌트 보고 재시도.

46분 45초 정답 통과

오답

• 의도: 주어진 단어의 뒤에 최소한의 글자를 추가해 최소 팰린드롬 길이 출력
  • 투 포인터 탐색
  • 양 끝의 글자가 같으면 그대로 진행
  • 다르면 맨 뒤에 글자를 추가했다는 전제로 왼쪽 포인터 이동, 전체 길이 증가
  • 두 포인터가 만나면 종료
• 예시
  1. qwe rty
  2. qwe r ty-
  3. qwer ty--
  4. qwer t y---
  5. qwert y----
  6. qwert y -----
• 반례: abaabaccdaba
• 안 되는 이유: 단어의 맨 뒤에 글자를 추가한다면 처음부터 팰린드롬 검사를 다시 해야 하는데, 이 코드는 당연히 될 거라 전제하고 이어서 진행했다.

def min_palindrome(word: str) -> int:
    ans_len = len(word)
    left = 0
    right = ans_len - 1

    while True:
        if left >= right:
            break
        if word[left] != word[right]:
            ans_len += 1
        else:
            right -= 1
        left += 1

    return ans_len

print(min_palindrome(input()))

첫 번째 정답

팰린드롬이 아닌 것이 확인될 때마다 그 횟수만큼 단어의 뒤에 빈 글자를 추가한 후, 그 빈 글자를 팰린드롬의 정의에 맞게 채우고 다시 팰린드롬 검사. 팰린드롬이 될 때까지 반복.

• 특징: 필요한 건 단어의 길이뿐인데 팰린드롬 단어를 진짜로 다 만든다.
• 단점: 그래서 코드가 길고 불필요한 정보를 너무 많이 만든다.

def min_palindrome(word: str) -> int:
    edited_word = word
    num_char = 0

    while not is_pal(edited_word):
        num_char += 1
        edited_word = fill_pal(word + ('-' * num_char))

    return len(edited_word)

def fill_pal(word: str) -> str:
    word_lis = list(word)
    for i in range(len(word_lis) - 1, -1, -1):
        if word_lis[i] == '-':
            word_lis[i] = word_lis[len(word_lis) - 1 - i]
    return to_string(word_lis)

def to_string(lis: list) -> str:
    word = ''
    for char in lis:
        word += char
    return word

def is_pal(word: str) -> bool:
    for i in range(len(word) // 2):
        if word[i] != word[len(word) - 1 - i]:
            return False
    return True

print(min_palindrome(input()))

두 번째 정답

• 개선한 부분: 불필요한 정보를 만들지 않도록 하기 위해 단어의 뒤에 채운 빈 글자를 그대로 두고 팰린드롬을 검사하게 했다. 실행 시간은 이전 정답보다 4ms 감소했다.

def min_palindrome(word: str) -> int:
    while not is_pal(word):
        word += '-'
    return len(word)

def is_pal(word: str) -> bool:
    for i in range(len(word) // 2):
        if word[len(word) - 1 - i] == '-':
            continue
        if word[i] != word[len(word) - 1 - i]:
            return False
    return True

print(min_palindrome(input()))