[Leetcode/파이썬] 3_Longest Substring Without Repeating Characters 문제풀이

 

문제 설명 

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

 

 

 

 

사고 흐름

1. 문자열이니까 바로 투포인터 생각

2, 완전 탐색으로 중복 확인하면서 포인터 증가시켜야겠다 

 

문제 핵심과 알고리즘

투포인터를 사용한 완전 탐색 

 

class Solution:
    def lengthOfLongestSubstring(self, string: str) -> int:
        left, right = 0, 1
        max_len = 1
        if len(string)==0 :
            return 0
        
        for i in range(len(string)) :
            left, right = i, i+1
            temp = string[left]
            while right<len(string) and string[right] not in temp :
                temp += string[right]
                right+=1
            max_len = max(max_len, right-left)
        return max_len

 

문자열 시작인 left에서 중복 문자가 없을때가지 right를 증가해 left 시작에서 최대 문자열을 찾는다. 이걸 for을 돌면서 모든 문자열을 확인한다. 

 

문제 풀면서 헤맸던 부분

처음에는 중복 문자가 있는지 확인하는 코드를

while right<len(string) and len(set(string[left:right]))==right-left :

 

이런 식으로 작성했다. 근데 시간이 3000ms 정도 걸려서 어디서 그렇게 오래걸리나 싶었는데 아마 매번 문자열을 set으로 만드는 것에 시간이 많이 걸렸다고 판단해 이 부분의 코드를 고쳤다. set으로 만드는 대신에 문자열을 하나씩 붙여가는 temp를 사용했다. 그러니 시간이 300ms로 줄었다. 헤헤

 

총평 

예전에는 풀지 못했던 문제였는데 비슷한 문제를 많이 풀어서 그런가 자연스럽게 투포인터를 떠올리고 풀었다. 아주 굿~