Longest Palindrome
대문자와 소문자가 포함된 문자열 s가 주어집니다. 문자를 재배열하여 만들 수 있는 가장 긴 회문을 만들고 그 회문의 길이를 반환하세요. 문자는 어떤 순서로든 배치할 수 있고 일부는 사용하지 않아도 되지만, 각 문자는 s에 나타난 횟수만큼만 사용할 수 있습니다.
대문자와 소문자는 서로 다른 문자이므로 Aa는 회문이 아닙니다.
함수
- sstring
- 사용할 수 있는 대문자 및 소문자
- 반환값integer
- 해당 문자들로 만들 수 있는 가장 긴 회문의 길이
제약 조건
1 ≤ s.length ≤ 5 × 104s에는 영어 문자a부터z까지와A부터Z까지만 포함됩니다.- 모든 글자를 다 사용할 필요는 없습니다.
예제
- 입력
- s = "coddyCode"
- 출력
- 5
- 설명
o는 두 번,d는 세 번 나타나고 나머지는 한 번씩 나타납니다.o두 개와d두 개, 그리고 가운데 남은 글자 하나를 합치면 길이가 5가 됩니다. 예를 들면doCod입니다.
- 입력
- s = "Aa"
- 출력
- 1
- 설명
A와a는 서로 다른 문자이므로 일치하는 쌍이 없습니다. 문자 하나만으로도 길이가 1인 회문입니다.
- 입력
- s = "xxxyyy"
- 출력
- 5
- 설명
- 두 개의
x와 두 개의y가 짝을 이루고, 남은 문자 하나는xyxyx처럼 가운데에 옵니다. 마지막y는 짝이 없으므로 제외됩니다.
후속 질문
여전히 O(n) 시간 안에 가장 긴 회문 자체와 그 길이를 함께 반환할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
회문은 양쪽 끝에서 읽어도 똑같습니다. 첫 글자는 마지막 글자와, 두 번째 글자는 끝에서 두 번째 글자와 짝을 이루는 식입니다. 각 글자가 몇 개씩 들어 있는지에 대해 무엇을 알 수 있나요?
정확히 가운데에 올 수 있는 문자 하나를 제외한 모든 문자는 짝을 이룹니다. 따라서
s의 순서는 전혀 중요하지 않고, 각 문자가 몇 번 나타나는지만 중요합니다.각 문자의 개수를 세세요. 각 개수에서 가장 큰 짝수 부분은 쌍으로 이루어지므로, 각 개수를 짝수로 내림한 값을 더하세요. 개수 중 홀수가 있으면 남은 문자 하나를 가운데에 놓을 수 있습니다. 이때 1을 한 번 더하세요.
풀이
재배열할 수 있으므로 s의 순서는 중요하지 않고, 각 문자가 몇 번 나타나는지만 중요합니다. 회문에서는 가운데에 있는 최대 한 글자를 제외하고 모든 글자가 반대편에 거울처럼 짝을 이룹니다. 따라서 글자 수를 세고, 각 쌍을 남긴 다음, 남는 글자가 있으면 가운데에 하나를 추가하세요.
이웃한 항목 정렬 및 짝짓기
핵심 아이디어
정렬하면 같은 문자끼리 서로 옆에 놓여 각 쌍이 나란히 위치합니다. xxxyyy에서 인덱스 0과 1의 x는 일치합니다. 쌍을 하나 만들고 두 칸 이동합니다. 인덱스 2에서는 x와 y가 다르므로 해당 x는 짝을 이루지 못한 채 남고 한 칸 이동합니다. 인덱스 3과 4의 y는 두 번째 쌍을 이루고, 마지막 y는 짝이 없습니다. 두 쌍으로 4를 얻고 가운데 문자 하나를 더해 5가 됩니다.
쌍을 만드는 데 n개의 문자를 모두 사용하지 않은 경우에만 문자가 남으므로 별도의 플래그는 필요하지 않습니다. 정렬에는 O(n log n) 시간이 들고, 정렬된 복사본에는 O(n) 공간이 필요합니다.
알고리즘
s의 문자를 정렬합니다.- 인덱스
i를 사용해 정렬된 문자를 순회합니다.i와i+1위치의 문자가 같으면 길이에 2를 더하고 두 칸 이동합니다. 그렇지 않으면 한 칸 이동합니다. - 길이가 문자 수보다 작으면 가운데 문자에 대해 1을 더합니다.
- 길이를 반환합니다.
def longestPalindrome(s):
letters = sorted(s)
n = len(letters)
length = 0
i = 0
while i + 1 < n:
if letters[i] == letters[i + 1]:
length += 2 # a pair: one copy on each side of the middle
i += 2
else:
i += 1
# A letter left without a partner can stand alone in the middle
if length < n:
length += 1
return length각 글자를 세어 보세요
핵심 아이디어
정렬하지 않아도 개수를 세면 같은 정보를 얻을 수 있습니다. 문자 코드마다 카운터를 하나씩, 총 128개 두면 A와 a는 서로 다른 카운터에 들어갑니다. c번 나타나는 문자는 짝수로 내림한 c개의 문자를 제공합니다.
coddyCode에서는 o와 d의 쌍이 4개의 문자를 제공합니다. 문자 5개가 남고, 그중 어느 것이든 가운데에 놓일 수 있습니다. 따라서 경우의 수는 5입니다. 짝을 이루지 못한 문자가 하나 더 있으면 거울 대칭을 이룰 수 없습니다.
s를 한 번 순회하며 카운터를 채우고 128개의 카운터를 한 번 순회하며 쌍의 수를 더합니다. 따라서 시간 복잡도는 O(n)이고 추가 공간 복잡도는 O(1)입니다(R에서는 먼저 s를 코드 벡터로 변환하므로 O(n)입니다).
알고리즘
- 0으로 설정된 카운터 128개를 만들고,
s의 각 글자에 해당하는 카운터에 1을 더합니다. - 각 카운터의 개수를 짝수로 내림한 값을 길이에 더합니다.
- 길이가
s의 길이보다 작으면 일부 개수가 홀수이므로 가운데 글자를 위해 1을 더합니다. - 길이를 반환합니다.
def longestPalindrome(s):
counts = [0] * 128 # one counter per character code, so 'A' and 'a' differ
for ch in s:
counts[ord(ch)] += 1
length = 0
for count in counts:
length += count // 2 * 2 # every pair fits, one copy on each side
# Fewer letters used than s has: some count is odd, so one letter can go in the middle
if length < len(s):
length += 1
return length
함정과 경계 사례
- 홀수 개수를 완전히 무시하기. 3번 나타나는 문자도 쌍 하나를 제공하므로,
xxxyyy의 결과는 1이 아니라 5입니다. - 홀수 개수마다 1을 더하기. 가운데에 들어갈 수 있는 문자는 하나뿐이므로,
xxxyyy의 결과는 6이 아니라 5입니다. A와a를 같은 문자로 취급하기.Aa에는 쌍이 없으므로, 답은 2가 아니라 1입니다.a부터z까지만 카운터의 크기를 설정하기. 대문자의 코드는 65부터 90까지이며 그 범위를 벗어납니다. 전체 문자 코드를 기준으로 인덱싱하세요.
자주 묻는 질문3
Longest Palindrome과 Longest Palindromic Substring은 어떻게 다른가요?
여기서는 글자 순서를 재배열할 수 있으므로 개수만 중요하며, 개수를 세면 O(n)에 해결할 수 있습니다. Longest Palindromic Substring은 이미 연속된 글자 덩어리로 나타나는 회문을 찾는 문제이며, 각 중심을 기준으로 확장하는 것과 같은 다른 방법이 필요합니다. abab의 경우 이 문제의 답은 4(abba)이고, 부분 문자열 버전의 답은 3(aba)입니다.
Longest Palindrome의 시간 복잡도는 얼마인가요?
계산을 사용하면 시간 복잡도는 O(n)입니다. 각 문자는 하나의 카운터를 1씩 증가시키며, 쌍의 개수를 모두 더할 때는 s의 길이와 관계없이 128개의 카운터를 읽습니다. 공간 복잡도는 O(1)입니다. 정렬한 다음 이웃한 항목끼리 짝을 짓는 방식은 시간 복잡도가 O(n log n)이고 공간 복잡도는 O(n)입니다.
s의 모든 문자를 사용해야 하나요?
아니요. 모든 쌍은 들어가고, 짝이 없는 문자는 최대 하나만 가운데에 들어갑니다. 따라서 홀수 개수로 나타나는 문자가 최대 하나일 때는 s의 길이가 답이고, 그렇지 않으면 s의 길이에서 홀수 개수로 나타나는 문자의 수를 뺀 다음 1을 더하면 됩니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def longestPalindrome(s):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
s = "coddyCode"
예상 출력
5