[문제출처 : Codechef] Lapindrome은 가운데를 기준으로 두 부분으로 나눴을 때, 등장하는 모든 글자들이 각각 동일한 빈도수를 가지고 등장하는 문자열을 의미합니다. 예를 들면, ‘gaga’라는 문자열은 lapindrome입니다. 가운데를 기준으로 ‘ga’와 ‘ga’가 동일한 빈도수의 문자들을 가지고 있기 때문이지요. 마찬가지로 ‘abccab’, ‘rotor’, ‘xyzxy’ 또한 lapindrome의 예입니다. 반면 ‘abbaab’는 ‘abb’와 ‘aab’로 나뉘는데, ‘a’와 ‘b’의 빈도수가 서로 다르기 때문에 이는 lapindrome이 아닙니다.
사실 두 부분으로 문자열을 나누는 것은 어렵지 않습니다. Python의 편리한 Slicing 기능을 사용하면 되기 때문이죠 :) 반면, 빈도수를 어떻게 비교할지에 대해서는 다양한 방법이 가능합니다.
Counter를 만들고, 왼쪽 절반에서 나오는 문자에 대해서는 +1을 하고, 오른쪽 절반에서 나오는 문자에 대해서는 -1을 해서 모든 value가 0인지를 확인합니다.- 각 반반씩 나뉜 문자열을 sorting한 후 두 문자열이 동일한지 파악합니다.
두 가지 모두 나쁘지 않은 방법이므로 모두 구현해 보겠습니다.
### 먼저 Counter를 사용하는 방법입니다.
from collections import defaultdict
def isLapindrome2(s):
counter = defaultdict(int)
# 한쪽 문자열에서는 +1을 해 나가고,
for i in range(len(s)/2):
counter[s[i]] += 1
# 다른쪽 문자열에서는 -1을 해 나갑니다.
secondHalf = len(s)/2 if len(s) % 2 == 0 else len(s)/2 + 1
for i in range(secondHalf, len(s)):
counter[s[i]] -= 1
# 그리고 모든 항목이 0인지를 확인합니다.
for key in counter:
if counter[key] != 0:
return False
return True
>>> print isLapindrome2("gaga")
True
>>> print isLapindrome2("abcde")
False
>>> print isLapindrome2("rotor")
True
>>> print isLapindrome2("xyzxy")
True
>>> print isLapindrome2("abbaab")
False
>>> print isLapindrome2("ababc")
False### 이번에는 간단하게 두 문자열을 sorting하여 비교하는 방법입니다.
def isLapindrome(s):
# 길이가 짝수이면 반반 나눠서 비교하고,
if len(s) % 2 == 0:
firstHalf = s[:len(s)/2]
secondHalf = s[len(s)/2:]
# 길이가 홀수이면 가운데 글자는 무시해도 됩니다.
else:
firstHalf = s[:len(s)/2]
secondHalf = s[len(s)/2+1:]
return True if sorted(firstHalf) == sorted(secondHalf) else False
>>> print isLapindrome("gaga")
True
>>> print isLapindrome("abcde")
False
>>> print isLapindrome("rotor")
True
>>> print isLapindrome("xyzxy")
True
>>> print isLapindrome("abbaab")
False
>>> print isLapindrome("ababc")
False