[Python 코테 입문] 3. (문제 4번) 팰린드롬 확인

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

 

섹션3. 해시(Hash)

 

(문제 4번) 팰린드롬 확인

소문자로만 이루어진 문자열이 주어지면 해당 문자열의 문자들의 순서를 재배치해서 팰린드롬(회문)을 만들 수 있는지를 확인하고 싶습니다. 만약 "abbac"와 같은 문자들을 "abcba"로 재배치하면 팰린드롬을 만들 수 있습니다.

매개변수 s에 문자열이 주어지면 해당 문자열이 재배치를 통해 팰린드롬을 만들 수 있으면 True를, 만들 수 없으면 False를 반환하는 프로그램을 작성하세요.

 

입출력 예

s	answer
"abacbaa"	True
"abaaceeffkckbaa"	True
"abcabbcc"	False
"sgsgsgabaaaecececekefefkccckbsgaaffsgsg"	True
"aabcefagcefbcabbcc"	False

 

제한사항

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

 

풀이

분석

Counter() 함수로 문자의 빈도수를 구한다.

팰린드롬을 만들 수 있으려면 빈도수가 홀수인 문자가 없거나 1개만 존재해야 한다. (회문의 중심부에 오는 문자만 빈도수가 홀수 또는 짝수로 존재할 수 있다.)

빈도수가 홀수인 문자가 1개 이하면 True를, 1개 초과면 False를 반환한다.

 

풀이

from collections import Counter

def solution(s):
  count = Counter(s)
  oddCount = 0
  for val in count.values():
    if val % 2 != 0:
      oddCount += 1
  if oddCount > 1:
    return False

  return True
  
print(solution("abacbaa"))
print(solution("abaaceeffkckbaa"))
print(solution("abcabbcc"))
print(solution("sgsgsgabaaaecececekefefkccckbsgaaffsgsg"))
print(solution("aabcefagcefbcabbcc"))

True
True
False
True
False

 

정답 풀이

분석

앞에서부터 읽으나 뒤에서부터 읽으나 똑같은 문자열을 팰린드롬(회문)이라고 한다.

팰린드롬을 만드려면 양쪽에 같은 문자를 대칭으로 배치해야 하며, 중심부에 오는 문자만 홀수로 존재할 수 있다.

즉, 모든 문자의 빈도수가 짝수이거나 오직 하나의 문자만 빈도수가 홀수여야 한다.

 

풀이

from collections import Counter

def solution(s):
  # 입력으로 받은 문자열의 각 문자의 빈도수를 구한다.
  count = Counter(s)
  # 빈도수가 홀수인 문자의 개수를 구한다.
  odd = 0
  for key in count:
    if count[key] % 2 == 1:
      odd += 1
      
  # 빈도수가 홀수인 문자가 1개 이하일 때에만 True를 반환한다.
  return odd <= 1
  
print(solution("abacbaa"))
print(solution("abaaceeffkckbaa"))
print(solution("abcabbcc"))
print(solution("sgsgsgabaaaecececekefefkccckbsgaaffsgsg"))
print(solution("aabcefagcefbcabbcc"))

True
True
False
True
False