[알고리즘] - 반복되지 않는 문자

문제 링크

https://www.geeksforgeeks.org/dsa/given-a-string-find-its-first-non-repeating-character/

문제

Q. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 
이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 
만약 그런 문자가 없다면 _ 를 반환하시오.

input = "abadabac"

def find_not_repeating_first_character(string):
    # 이 부분을 채워보세요!
    return "_"

result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

정답 풀이

input = "abadabac"

def find_not_repeating_first_character(string):
    for i in range(len(string)):
        is_unique = True
        for j in range(len(string)):
            if i != j and string[i] == string[j]:
                is_unique = False
                break
        if is_unique:
            return string[i]
    return "_"

result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

input = "abadabac"

def find_not_repeating_first_character(string):
    alphabet_occurence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')
        alphabet_occurence_array[arr_index] += 1

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

        if alphabet_occurrence == 1:
            not_repeating_character_array.append(chr(ord('a') + index))

    for char in string:
        if char in not_repeating_character_array:
            return char

    return "_"

result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

문제를 풀고 알게 된 개념 및 소감

• 첫번째 풀이의 경우 flag 변수를 사용할 생각을 못했던 것 같다.
• 두번째 풀이의 경우 반복되는지 아닌지를 확인하기 위해, 알파벳 별로 출현하는 횟수를 저장한다. 배열에 빈도수를 저장하고, 배열을 돌면서 반복되지 않는 문자를 집어 넣는다. 그리고 string 을 돌면서 첫번째 반복되지 않는 문자를 찾아 반환하면 된다.