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

이것도 오늘 들었던 강의내용의 문제!

 

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

input = "abadabac"

input을 보면

a는 4번이 나오고,

b는 2번이 나오고,

d는 1번,

c도 1번이 나온다.

 

d와 c처럼 한번씩만 나오는 문자들 중, 가장 첫번째로 등장하는 문자를 찾는 문제! (여기서는 'd')

 

input = "abadabac"

def findNotRepeatingCharacter(string):

#구현

    return 0


result = findNotRepeatingCharacter(input)
print(result)

이 함수 내부를 구현하면 된다!

 

어떻게 풀지 생각하다보면 감이 오겠지만 시간복잡도가 가장 중요한 문제다.

O(nlogn)이상이라면 알고리즘을 다시 생각해보도록 하자!

 

 

 

 

 

 

pseudo code 의사코드

 

1. 반복되는 문자인지 확인

  1) 반복 횟수를 문자와 함께 저장

 

2. 1-1)의 내용을 수행할 자료구조 선택 

  1) 리스트 ?

  2) 딕셔너리?

 

3. 반복되지 않은 문자들의 순서를 등장순으로 정렬

  1) 딕셔너리를 사용 하면 정렬할 필요가 없음

 

 

 

 

전체 코드

 

input = "abadabac"

def findNotRepeatingCharacter(string):
    dic = {}
    result = '_'

    for i in range(len(string)):

        # if dic[string[i]] == 1: 		#오류가 발생하는 문법
        # if dic[string[i]] is not None: 	#오류가 발생하는 문법
        if string[i] in dic: 	#문자가 딕셔너리의 키에 이미 있으면, 값을 1 증가
            dic[string[i]] += 1
        else:			#그 이외는 딕셔너리에 키와 값 추가
            dic[string[i]] = 1

    for n in dic:		#딕셔너리는 저장된 순서대로 이미 정렬되어있따
        if dic[n] == 1:
            result = n
            break

    return result


result = findNotRepeatingCharacter(input)
print(result)

 

풀고나니 이번 문제는 강의 내용의 풀이와 매우 다르게 풀었다. 강사님께서는 리스트를 사용하셨다!

 

시간복잡도는 2n 정도로 이정도면 O(n)을 빠르게 맞췄다고 생각한다..! 

 

주석으로 오류가 발생하는 문법을 두줄 남겨놓았다! 저 부분이 가장 걸림돌이었어서 복기차원에서 그냥 두었따

아직 python 문법이 약하다보니 구현할 때 오류를 자주 낸다...