[LeetCode] 3번 Longest Substring Without Repeating Characters 문제 풀이 (파이썬)

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

DP를 활용해야 하는 문제인 것 같기는 했는데, 아직 해당 유형을 많이 풀어본 적이 없는지라 어떻게 풀어야 할지 막막해서 계속 코드를 썼다 지웠다 하고 종이에 그림도 그렸다 포기도 했다 온갖 짓을 반복한 끝에 나름대로 풀이법을 떠올렸다.

 

접근

문자열의 각 문자를 마지막 문자로 하는 부분 문자열을 찾아, 이의 최대 길이를 찾아 이를 dp 테이블에 저장해준다는 것을 핵심 아이디어로 가져갔다.

이 경우 특정 인덱스의 문자를 확인할 때 맨 앞에서부터 모든 경우의 수를 다 확인해볼 필요 없이 바로 앞 인덱스에서의 부분 문자열만 확인해주면 된다.

즉, i - 1번째 문자를 마지막 문자로 하는 부분 문자열 tmp에서 i번째 문자와 중복되는 문자가 있는지 확인한 후, 없다면 i번째 문자를 tmp에 추가한다. 있다면 tmp에서 중복되는 문자 이전을 지운 후 tmp에 i번째 문자를 추가한다.

 

개선사항

문제는 풀리긴 했지만 개선 사항이 있어 보인다. 우선 매번 특정 문자가 부분 문자열에 있는지 확인(if s[i] in tmp)해주는 과정과, 부분 문자열에 중복되는 문자가 있다면 그 인덱스를 찾아주는 과정(tmp.index(s[i]))에서 각각 O(n)의 시간 복잡도가 소요되기 때문이다.

이전 고민 과정들에서 투 포인터를 사용하는 방법도 생각해보았는데, 이를 적용할 수 있으면 좋을 것 같다. 또한 탐색에 O(1)이 소요되는 딕셔너리를 활용한다면 시간복잡도를 줄일 수 있을 것 같다.

 

풀이

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
    
        # 빈 문자열이 들어왔을 경우 0 리턴
        if len(s) == 0:
            return 0
            
        # 각 인덱스의 원소를 마지막 문자로 하는 부분 문자열의 최대 길이를 저장해줄 dp 테이블 초기화
        d = [0] * len(s)
        
        # 첫 번째 문자에 대하여 dp 테이블 업데이트, 부분 문자열 tmp에 저장
        d[0] = 1
        tmp = s[0]
        
        # 두 번째 문자부터 모든 문자에 대하여
        for i in range(1, len(s)):
            # 만약 기존 부분 문자열에 i번째 문자와 중복된 문자가 있다면
            if s[i] in tmp:
                idx = tmp.index(s[i]) # 부분 문자열에서 중복된 문자의 인덱스를 찾아
                tmp = tmp[idx + 1:] # 중복이 있는 부분 이전을 제거해준다.
            tmp += s[i] # 새 문자를 포함한 부분 문자열로 업데이트
            d[i] = len(tmp) # dp 테이블에 부분 문자열의 길이를 업데이트
            
        return max(d)