알고리즘 더 풀어보기 (2)

[반복되지 않는 문자]

다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오.

만약 그런 문자가 없다면 _ 를 반환하시오.

"abadabac" # 반복되지 않는 문자는 d, c 가 있지만 "첫번째" 문자니까 d를 반환해주면 됩니다!

 

각 알파벳이 각각 몇 개 나왔는지 각각의 값을 가지고 있는 배열을 만들고

1번 나온 알파벳들은 새로운 배열에 저장함

문자열과 1번나온 알파벳만 들어있는 배열과 비교해서

배열에 들어있는 문자가 문자열에서 나오는 순간 리턴

 

input = "abadabac"


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

    for char in string:
        if char.isalpha():
            index = ord(char) - ord('a')
            alphabet_occurrence_array[index] += 1

    not_repeating_character_array = []
    for i in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[i]
        if alphabet_occurrence == 1:
            not_repeating_character_array.append(chr(i + ord('a')))

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


result = find_not_repeating_character(input)
print(result)

 

[시간복잡도]

O(N)

함수 구문 하나하나를 보지 않더라도

1차 반복문이 나왔고 array길이 만큼 반복한다면

O(N)이다 라고 생각하면 됨

다른 계수는 다 버려버려도 됨 영향을 주지 않음