알고리즘 : 기본 예제, 빈도수 찾기

어느 한 문제를 해결하는 데 두 가지 방식이 있다.

보다 효과적인 알고리즘을 찾기 위해서 고려해야할 것은 무엇일까?

먼저, 다음 문제를 해결해보는 시간을 가져보고,

 

어느 방식이 효율적일지 고려해보는 시간을 갖는다.

 

 

 

본격적으로 문제를 풀어보기에 앞서, 어떤 알파벳이 가장 많이 포함되어있는지 반환해보는 문제를 풀어본다.

 

알파벳 빈도수 찾아보기.

def find_alphabet_occurrence_array(string):
    alphabet_occurrence_array = [0] * 26

    # 이 부분을 채워보세요!

    return "a"


print(find_alphabet_occurrence_array("hello my name is sparta"))

 

해법

 

def find_alphabet_occurrence_array(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha(): # 알파벳이 아니라면 (첫째로 알파벳인지부터 확인하기)
            continue #반복문의 다음 인덱스로 넘어가게 한다.(알파벳이 아니면 다음 문자를 보도록 한다)
        arr_index = ord(char) - ord("a")  # 아스키 코드 이용, 내장 함수 ord() 이용하여 아스키 값을 활용, 이 값들의 차를 arr_index에 저장받기
        alphabet_occurrence_array[arr_index] += 1  #변수char가 배열string를 돌면서 대응하는 알파벳 순서에 1을 더해줌. 즉 알파벳 수만큼 카운트
# 각 char에 따른 arr_index를 구하고, 그 arr_index를 가진 alphabet_occurrence_array의 값을 하나씩 증가시킴으로써, 알파벳별 빈도수를 업데이트함
    return alphabet_occurrence_array   #for문이 끝나고 반환함

print(find_alphabet_occurrence_array("hello my name is sparta"))

실행결과 ==> 

[3, 0, 0, 0, 2, 0, 0, 1, 1, 0, 0, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0]

 

(hello my name is sparta에 a가 세 개니까 3, e는 두 개니까 2....)

 

 

 

문자열의 최빈값인 알파벳을 출력하기

첫 번째 방식 풀이

input = "hello my name is sparta"

# 알파벳을 문자열과 하나하나 비교하며, 몇 번 나왔는지 검사하는 코드를 작성
def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m",
                      "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
    #알파벳의 배열을 지정해놓음
    
    max_occurrence = 0  # 최고로 많이 나온 횟수 저장하는 변수
    max_alphabet = alphabet_array[0]  # 최고로 많이 나온 알파벳을 저장하는 변수

    for alphabet in alphabet_array:  # for문을 이용하여, 알파벳을 하나씩 꺼내봄
        occurence = 0
        for char in string:
            if char == alphabet:  # 문자열에 있는 문자와 동일하다면
                occurence += 1    # occurence를 하나씩 증가시켜

        if occurence > max_occurrence:    
            max_occurrence = occurence   # 더 큰 값을 발견하면 max_occurrence를 업데이트함
            max_alphabet = alphabet      # max_alphabet에 해당하는 알파벳을 찾아 저장함
            
    return max_alphabet  # 이 방법을 통해서 마지막에 반환하는 것은 max_alphabet


result = find_max_occurred_alphabet(input)
print(result)

실행결과==>

a

 

 

두 번째 방식 풀이

def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha(): # 알파벳이 아니라면 (첫째로 알파벳인지부터 확인하기)
            continue #반복문의 다음 인덱스로 넘어가게 한다.(알파벳이 아니면 다음 문자를 보도록 한다)
        arr_index = ord(char) - ord("a")  # 아스키 코드 이용, 내장 함수 ord() 이용하여 아스키 값을 활용, 이 값들의 차를 arr_index에 저장받기
        alphabet_occurrence_array[arr_index] += 1  #변수char가 배열string를 돌면서 대응하는 알파벳 순서에 1을 더해줌. 즉 알파벳 수만큼 카운트
# 각 char에 따른 arr_index를 구하고, 그 arr_index를 가진 alphabet_occurrence_array의 값을 하나씩 증가시킴으로써, 알파벳별 빈도수를 업데이트함

    max_occurrence = 0  # 가장 많은 빈도수를 저장하는 변수
    max_alphabet_index = 0 # 가장 많이 나온 알파벳의 인덱스를 저장하는 변수
    for index in range(len(alphabet_occurrence_array)) :  #for문을 돌려 하나씩 비교
        # index가 0이면 -> alphabet_occurrence는 3
        alphabet_occurrence = alphabet_occurrence_array[index]  #alphabet의 빈도수를 하나씩 꺼내봄

        if alphabet_occurrence > max_occurrence:
            max_alphabet_index = index
            max_occurrence = alphabet_occurrence
    print(max_alphabet_index)
    return chr(max_alphabet_index + ord("a"))

result = find_max_occurred_alphabet
print(result("Hello my name is sparta"))

실행결과==>

0

a