[LeetCode 3] Longest Substring Without Repeating Characters 풀이

문제 : 단어 변수 s를 받고 반복되지 않는 글자 수의 최댓값 return 하기

예시 : "abcabcbb" 에서 "abc" 가 중복되지 않으면서 글자수가 가장 김. 따라서 답은 3

풀이 :

변수 초기값 설정한다. 

• used : 사용한 알파벳과 위치를 저장하기 위한 빈 dictionary
• max_length : 최대 단어 길이
• start : 단어 길이를 재기 위한 시작 위치

used = {}
max_length = start = 0

단어를 loop에 넣는다. 알파벳 길이를 쉽게 알기 위해 enumerate를 씌운다. 

for idx, c in enumerate(s):

아래 코드부터는 모두 loop 안에 들어간다.

딕셔너리에 순번인 알파벳(c)이 들어있고, 그 알파벳의 기존 위치가 start 변수 값보다 크면 / 뒤에 있으면 start 값을 업데이트 한다.  (설명 : 딕셔너리에 있다는 것은 앞에서 나왔던 알파벳이라는 것을 의미하며, 중복되므로 위치를 새롭게 하여 카운트 해야 한다 )

    if c in used and start <= used[c]: 
        start = used[c] + 1

그 외의 경우 (처음 나오는 알파벳이거나 start 값이 저장된 값보다 큰 / 뒤에 있는 경우) 기존 길이와 현재 길이를 대조하여 저장한다.

    else: 
        max_length = max(max_length, idx - start + 1)

 

딕셔너리에 알파벳 위치를 index로 업데이트 한다.

    used[c] = idx

 

'abcabcbdab' 을 넣어보고 프린트 구문으로 추적해보자. 

 

s = 'abcabcbdab'

used = {} #단어별 loop 마지막 위치 
max_length = start = 0 #초기값
for idx, c in enumerate(s): #단어 loop
    if c in used and start <= used[c]: #예전에 나왔고 start가 마지막으로 나온 단어 위치보다 앞이면
        start = used[c] + 1 #start 업데이트
        print('if  ','idx:',idx,'/c:',c,'/used:',used,'/start:',start,'/max_length:',max_length)
    else: #그 외 (알파벳이 처음나오거나 start가 c 뒤에 있으면
        max_length = max(max_length, idx - start + 1) #기존의 최대 길이와 대조하여 최댓값 업데이트
        print('else','idx:',idx,'/c:',c,'/used:',used,'/start:',start,'/max_length:',max_length)

    used[c] = idx

비고 : 내가 한 방식은 loop돌리며 글자를 리스트에 저장하고 중복되는 글자가 나오면 리스트 리셋하는 방식이었다. 테스트  할 수록 예외사항을 발견하고 코드가 복잡해 졌는데 위의 풀이가 간결하면서 깔끔하다. 저런 아이디어를 발상하기 위해 더 많은 코드를 짜보고 대조해보고 시간이 지난 후에 다시 다듬는 방식으로 고도화 시켜야겠다.