코딩 인터뷰 완전 분석 1.4 파이썬3 풀이

문제

1.4 회문 순열: 주어진 문자열이 회문(palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며, 순열이란 문자열을 재배치하는 것을 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다.

 

입력: Tact Coa

출력: True (순열: “taco cat”, “atco cta” 등)

 

제한 사항

1. 문자에 대한 제한은 없는가? (알파벳을 제외하고도, 아스키 코드 범위)
2. 대문자와 소문자를 같은 문자로 취급한다.
3. 공백은 무시해도 되는 것인가?

 

아이디어1

문자가 키가 되는 해시테이블을 생성한다.

각 문자의 출현 빈도를 값에 담는다.

홀수 개의 문자의 개수를 조사한다.

홀수 개의 문자가 1개 이하이면 True이다.

 

공간복잡도

O(n) 보다 작다.

 

시간복잡도

O(n)

 

아이디어2

정렬을 하고 비교하면 적어도 O(nlogn)이고,

모든 순열의 경우의 수를 보면 O(n!)되므로,

아이디어1 만한게 없는 거 같다.

 

테스트케이스

True 경우

• ‘a’
• ‘aaaaaabbbb’
• ‘ I love you i love you ‘
• ‘kkkkabbbb‘
• ‘ aaakkkkbbbb’

False 경우

• ‘ac’
• ‘aaaaaabbbbb’
• ‘ I love you i love you kz ‘
• ‘kkkkabbbbb‘
• ‘ aaakkkkbbbbc’

 

코드

def is_palindrome(example):

    example = example.lower()

    char_table = {}
    num_of_odd = 0

    for char in example:
        if char != ' ':
            char_table[char] = 0

    for char in example:
        if char != ' ':
            char_table[char] += 1

    for value in char_table.values():
        if value % 2 == 1:
            num_of_odd += 1

    if num_of_odd < 2:
        return True
    else:
        return False


# True 경우
print(is_palindrome('a'))
print(is_palindrome('aaaaaabbbb'))
print(is_palindrome(' I love you i love you '))
print(is_palindrome('kkkkabbbb'))
print(is_palindrome(' aaakkkkbbbb'))

# False 경우
print(is_palindrome('ac'))
print(is_palindrome('aaaaaabbbbba'))
print(is_palindrome(' I love you i love you kz '))
print(is_palindrome('kkkkabbbbb'))
print(is_palindrome(' aaakkkkbbbbc'))

 

힌트

#106 모든 순열을 전부 생성할 필요가 없다. 아주 비효율적이다.

#121 어떤 문자열이 회문의 순열일 때, 그 특성은 무엇인가?

#134 해시테이블을 사용해 본 적이 있는가? O(n) 시간으로 줄일 수 있다.

#136 비트 벡터를 사용해서 공간을 줄일 수 있는가?

 

해답

비트 벡터에 대한 고찰이 필요. 시간복잡도는 줄이기 어렵지만 반복문의 형태를 바꾸어 어떤 것이 더 빠를지 논의해보는 것도 방법.