[알고리즘] base case로부터 확장하기, 회문 순열 여부 확인하기

 

1. Base Case로부터 확장하기

 

 

n = 1 일 때와 같은 base case에 대한 문제를 해결한 뒤에 거기서부터 한단계씩 문제를 확장해 나가는 방식이다.

 

 

from copy import copy

# 문자열의 모든 순열을 계산하는 알고리즘을 설계하라
# 모든 문자는 문자열 내에서 고유하게 등장한다고 가정

string = ['a', 'b', 'c', 'd']


def find_permutations(_list):
    # base case
    if len(_list) == 1:
        return [_list]

    last = _list.pop()

    base_elements = find_permutations(_list)

    combined_elements = []

    for element in base_elements:
        for j in range(len(element) + 1):
            base_for_combination = copy(element)
            base_for_combination.insert(j, last)
            combined_elements.append(base_for_combination)
            
    return base_elements + combined_elements + [[last]]


find_permutations(string)

 

 

주어진 문자열 'abcd' 의  모든 순열을 구하는 알고리즘을 설계한다고 할 때 

 

base case에 해당하는 문자열 'a' 의  순열은 {'a'} 이고

 

'ab'의 순열은 a의 결과값인 {'a'}의 앞뒤에 'b'가 삽입되는 형식으로 진행되므로 이를 반복하면 문제를 해결할 수 있다.

 

 

 

 

2. 회문 순열 여부 확인하기.

 

 

 

회문이란 뒤집어 읽어도 같은 단어 혹은 문장을 말한다.

 

 

단어를 뒤집었을 때도 같은 단어가 되려면

 

단어의 길이가 짝수일 경우 각 문자의 개수가 모두 짝수여야 하고,

 

단어의 길이가 홀수일 경우 한 문자 만이 홀수여야 한다.

 

 

def check_palindrome(string):
    element_count_dic = {}

    # 문자열에 속한 문자의 갯수를 딕셔너리에 저장
    for element in string:
        if element in element_count_dic:
            element_count_dic[element] += 1
        else:
            element_count_dic[element] = 1

    # 문자열의 길이가 짝수라면, 각 문자의 개수가 모두 짝수인지 확인
    if len(string) % 2 == 0:
        for element in element_count_dic:
            if element_count_dic[element] % 2 != 0:
                return False

    # 문자열의 길이가 홀수라면, 홀수인 원소가 하나만 존재하는 지 확인
    else:
        odd_count = 0

        for element in element_count_dic:
            if element_count_dic[element] % 2 != 0:
                odd_count += 1
                if odd_count > 1:
                    return False
    return True

 

 

 

 

Cracking the Coding Interview (Gayle Laakmann McDowell) 의 글로 된 예제를 코드로 작성해 보았습니다.

 

책에 있는 코드가 아니므로 정답이 아닐 수 있습니다.