Python으로 문자를 제거·재배열해 만들 수 있는 가장 긴 회문 찾기

문자열이 하나 주어졌을 때, 문자열에서 문자를 삭제하거나 재배열(shuffle)하여 만들 수 있는 가장 긴 회문(palindrome)을 찾아야 합니다. 만약 만들 수 있는 회문이 여러 개라면 그중 하나만 반환하면 됩니다.

예를 들어 입력이 pqqprrs라면, 출력은 pqrsrqp가 됩니다.

접근 방법

회문은 왼쪽 절반과 오른쪽 절반이 거울상처럼 대칭을 이루는 문자열입니다. 따라서 각 문자를 짝수 개씩 좌우에 배치하고, 개수가 홀수인 문자는 최대 하나만 가운데에 둘 수 있습니다. 이 성질을 활용하면 다음과 같은 단계로 문제를 해결할 수 있습니다.

• 1단계: 크기가 256인 배열 count를 생성하고 모든 요소를 0으로 초기화합니다.

• 2단계: 문자열을 처음부터 끝까지 순회하면서 각 문자의 ASCII 코드에 해당하는 count 값을 1씩 증가시켜, 문자별 등장 횟수를 계산합니다.

• 3단계: 빈 문자열 begin, mid, end를 준비합니다.

• 4단계: character를 'a'의 ASCII 값으로 초기화한 뒤, 'z'의 ASCII 값 이하일 때까지 다음 과정을 반복합니다.

  • count[character]가 홀수라면(비트 연산 & 1의 결과가 0이 아니라면), 해당 문자를 mid로 지정하고 count[character]를 1 감소시킨 후 character를 1 감소시킵니다. 이렇게 하면 개수를 1 줄여 짝수로 만든 뒤, 다음 반복에서 같은 문자를 다시 처리하게 됩니다.

  • 그렇지 않다면(짝수 개라면), count[character] // 2번만큼 반복하면서 begin에 해당 문자를 추가합니다.

• 5단계: end를 begin과 동일하게 복사한 뒤, end를 뒤집습니다(reverse).

• 6단계: begin + mid에 해당하는 문자 + end를 순서대로 연결한 문자열을 반환합니다.

예제 코드

다음 구현을 통해 더 자세히 이해해 보겠습니다.

def get_palindrome(string):
    count = [0]*256
    for i in range(len(string)):
        count[ord(string[i])] += 1
    begin = ""
    mid = ""
    end = ""
    character = ord('a')
    while character <= ord('z'):
        if (count[character] & 1):
            mid = character
            count[character] -= 1
            character -= 1
        else:
            for i in range(count[character]//2):
                begin += chr(character)
        character += 1
    end = begin
    end = end[::-1]
    return begin + chr(mid) + end

string = "pqqprrs"
print(get_palindrome(string))

입력

"pqqprrs"

출력

pqrsrqp

참고 사항

이 알고리즘의 시간 복잡도는 문자열 길이를 n이라 할 때 O(n)이며, 고정된 크기의 256 크기 배열만 사용하므로 공간 복잡도는 O(1)입니다. 다만 위 코드는 소문자 알파벳(a~z)을 기준으로 동작하므로, 대문자나 숫자, 특수문자가 포함된 문자열을 처리하려면 문자 범위를 적절히 조정해야 합니다.