알고리즘과 친해지기 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 위치를 찾아서 아스키 코드에서 배열로 변환하는 과정이 훨씬 간단해 보였다.
'항해 중 > 알고 보면 알기 쉬운 알고리즘' 카테고리의 다른 글
공간 복잡도 판단하기 (0) | 2021.11.12 |
---|---|
시간 복잡도 판단하기 (0) | 2021.11.12 |
알파벳 빈도수 세기 (0) | 2021.11.12 |
최댓값 찾기 (0) | 2021.11.12 |
알고리즘이란? (0) | 2021.11.12 |
댓글