파이썬 알고리즘-75 중복되지 않은 알파벳으로 이루어진 제일 긴 단어의 길이

String 형인 str 인자에서 중복되지 않은 알파벳으로 이루어진 제일 긴 단어의 길이를 반환해주세요.

str: 텍스트
return: 중복되지 않은 알파벳 길이 (숫자 반환)

예를 들어,
str = "abcabcabc"
return은 3
=> 'abc' 가 제일 길기 때문

str = "aaaaa"
return은 1
=> 'a' 가 제일 길기 때문

str = "sttrg"
return은 3
=> 'trg' 가 제일 길기 때문

내 코드

def get_len_of_str(string):
    longest = 0
    for i in range(len(string)):
        res = ''
        cnt = 0
        for j in string[i:]:
            if j not in res:
                res+=j
                cnt+=1
            else:
                res=j
                cnt=1
            if cnt>longest:
                longest=cnt
    return longest

최초의 코드는 반복문을 한번만 돌았기 때문에 중간의 문자열을 체크할 수가 없어서 코드를 수정했다. 그 과정에서 시간복잡도가 O(N3)이 되었다.

풀이

def get_len_of_str(s):
    # 딕셔너리로 해싱
	dct = {}
	max_so_far = curr_max = start = 0
    # enumerate로 문자열의 인덱스와 문자를 돌려주고 이를 반복
	for index, i in enumerate(s):
        # 중복된 문자열을 찾았다면
		if i in dct and dct[i] >= start:
			max_so_far = max(max_so_far, curr_max)
            # 중복문자열을 찾은 인덱스 - 현재 문자열이 시작한 인덱스 를 통해 최대 길이를 구할 수 있음
			curr_max = index - dct[i]
            # 문자열의 출발점을 하나 뒤로 밀어줌
			start = dct[i] + 1 
        # 중복 문자열이 없다면
		else:
            # 길이+1
			curr_max += 1
        # 문자열을 탐색할 때마다 위치값을 저장
		dct[i] = index
	return max(max_so_far, curr_max)

반성점

• 딕셔너리는 생각도 하지 못했다.

배운 것