[Python 코테 입문] 3. (문제 5번) 팰린드롬 길이

🖥️ 입문자를 위한 코딩테스트 핵심 - Python (김태원, 인프런)

 

섹션3. 해시(Hash)

 

(문제 5번) 팰린드롬 길이

문자열이 주어지면 해당 문자열의 문자들을 가지고 만들 수 있는 최대길이 팰린드롬을 만들고 그 길이를 구하세요.

문자열은 소문자로만 이루어져 있습니다.

만약 "abcbbbccaaeee"가 주어진다면 만들 수 있는 가장 긴 팰린드롬은 "ecbbaaabbce"이고 답은 11입니다.

 

입출력 예

s	answer
"abcbbbccaaeee"	11
"aabbccddee"	10
"fgfgabtetaaaetytceefcecekefefkccckbsgaafffg"	41
"aabcefagcefbcabbcc"	17
"abcbbbccaa"	9

 

제한사항

• s의 길이는 1,000을 넘지 않습니다.

 

풀이

분석

빈도수가 짝수인 문자는 모두 포함한다.

빈도수가 홀수인 문자는 1을 뺀 개수만 포함한다. 빈도수가 홀수인 문자가 1개 이상일 때 최종 답에 1을 더해준다. (팰린드롬의 중심에는 홀수개인 문자가 올 수 있으므로)

 

풀이

from collections import Counter

def solution(s):
  answer = 0
  oddDict = dict()
  count = Counter(s)
  for key in count:
    if count[key] % 2 == 0:
      answer += count[key]
    else:
      oddDict[key] = count[key]
  for key in oddDict:
    answer += oddDict[key] - 1
  if len(oddDict) >= 1:
    answer += 1
  return answer
  
print(solution("abcbbbccaaeee"))
print(solution("aabbccddee"))
print(solution("fgfgabtetaaaetytceefcecekefefkccckbsgaafffg"))
print(solution("aabcefagcefbcabbcc"))
print(solution("abcbbbccaa"))

11
10
41
17
9

 

정답 풀이

분석

문자열에 빈도수가 홀수인 문자가 존재하지 않으면 전체 문자열의 길이를 반환한다.

빈도수가 홀수인 문자가 존재하면 그 중에서 1개만 전체 개수를 사용할 수 있고(팰린드롬의 중심에 위치), 나머지 문자들은 1개를 뺀 짝수개만 사용할 수 있다.

 

풀이

from collections import Counter

def solution(s):
  count = Counter(s)
  odd = 0
  for key in count:
    if count[key] % 2 == 1:
      odd += 1
  return len(s) - odd + 1 if odd > 0 else len(s)
  
print(solution("abcbbbccaaeee"))
print(solution("aabbccddee"))
print(solution("fgfgabtetaaaetytceefcecekefefkccckbsgaafffg"))
print(solution("aabcefagcefbcabbcc"))
print(solution("abcbbbccaa"))

11
10
41
17
9