최빈값 찾기

알고리즘과 친해지기 2 - 최빈값 찾기

: 위에서 풀었던 알파벳의 빈도수 세기를 활용해서 가장 많은 빈도수의 문자를 반환하는 문제이다.

 

1) 의사코드(수도코드)

 

- 최대값을 담을 변수 생성 => max

- 알파벳의 빈도 수를 담은 배열 생성

alphabet_occurrence_array = [0] * 26

- 문자인 지 아닌 지 구별하는 함수 => str.isalpha()를 사용해서 문자이면 true를 반환, 문자가 아니면 false를 반환

- 문자를 숫자(아스키 코드)로 변환하는 함수 => ord("문자")

- 해당 문자의 index 위치를 찾아서 1씩 더한다. => ord('a') - ord('a')를 하면 0이라는 index 값이 나온다.

- 배열을 돌면서 가장 큰 값을 가진 인덱스 위치를 찾는다.

- 해당 index에 'a'의 아스키 코드 값을 더해서 아스키 코드를 문자로 바꾼다.

- 해당 문자의 index 위치를 찾아서 1씩 더한다. => ord('a') - ord('a')를 하면 0이라는 index 값이 나온다.

- 빈도수를 담은 배열을 돌면서 최댓값을 찾아서 max 변수에 담는다.

- 최댓값의 인덱스 위치를 찾는다. => 배열.index(값)

- 최댓값에 a의 아스키 코드를 더해서 해당 인덱스의 아스키 코드를 반환한다. => ord('a')

- 아스키 코드 -> 문자로 변환 => chr(숫자)

 

문제 풀이

input = "hello my name is sparta"

def find_max_occurred_alphabet(string):

    alphabet_occurrence_array = [0] * 26
    max = 0

    # 문자열에서 문자를 하나씩 빼온다.
    for str in string:
        # 문자인 지 아닌 지 검사한다.
        if str.isalpha():
            # 해당 문자를 아스키 코드로 변환한다.
            index = ord(str)-ord('a')
            # 해당 index 값에 +1을 한다.
            alphabet_occurrence_array[index] += 1

    # 배열을 돌면서 최댓값을 찾아서 max 변수에 담는다.
    for alphabet in alphabet_occurrence_array:
        if max < alphabet:
            max = alphabet

    result = chr(ord('a') + alphabet_occurrence_array.index(max))
    # 배열.index(값) : 배열 안에서 값이 들어있는 index 위치를 반환한다.
    # ord('a') + index 위치 = 해당 인덱스의 아스키 코드 값이 나온다.
    # chr(숫자) : 아스키 코드 -> 문자로 변환

    return result

result = find_max_occurred_alphabet(input)
print(result)

 

선생님의 첫번째 문제 풀이

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", "x", "y", "z"]
    max_occurrence = 0
    max_alphabet = alphabet_array[0]

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:
            if char == alphabet:
                occurrence += 1
        if occurrence > max_occurrence:
            max_occurrence = occurrence
            max_alphabet = alphabet

    return max_alphabet

result = find_max_occurred_alphabet(input)
print(result)

 

선생님의 두번째 문제 풀이

input = "hello my name is sparta"

def find_max_occurred_alphabet(string):

    # 알파벳의 빈도 수를 담을 배열
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha(): # 문자가 아니라면
            continue # 반복문을 건너뛴다.
        else: # 문자라면
            arr_index = ord(char) - ord('a')
            alphabet_occurrence_array[arr_index] += 1

        max_occurence = 0
        max_alphabet_index = 0

        for index in range(len(alphabet_occurrence_array)):
            alphabet_occurrence = alphabet_occurrence_array[index]

            if alphabet_occurrence > max_occurence:
                max_alphabet_index = index
                max_occurence = alphabet_occurrence
    
    return chr(max_alphabet_index + ord('a'))

result = find_max_occurred_alphabet(input)
print(result)

 

내 생각에는 이 또한 두번째 방법이 더 효율적이라고 생각한다.

첫번째 방법에서는 배열에 알파벳을 각각 넣어서 그 알파벳의 빈도수와 빈도수가 가장 많은 알파벳을 변수에 담고 다시 배열과 비교하는 작업을 하다 보니 시간도 오래 걸리고 공간도 많이 잡아 먹는 것 같았는 데

두번째 방법은 내장 함수를 사용하여서 빈도수를 담는 배열을 따로 만들고 최대 빈도수를 가진 index 위치를 찾아서 아스키 코드에서 배열로 변환하는 과정이 훨씬 간단해 보였다.