문제 개요
-
중복된 문자열을 제거하고 최대 길이의 부분 문자열 길이를 반환하면 됩니다.
-
'abcabcbb'를 보면 중복 없는 최대 길이 부분 문자열은 abc가 되죠.
-
문제 자체는 심플합니다. 바로 어떻게 풀지 생각해 보시죠.
풀이 구상
-
우선 brute force(완전탐색)으로 찾는다면 답을 찾을 수는 있습니다.
-
다만 O(n^2)으로 시간초과가 발생합니다. 따라서 더 효율적인 방법을 써야합니다.
-
바로 떠올릴 수 있는 것은 two pointer입니다.
-
start, end 포인터를 움직이며 최대 길이를 구할 수 있습니다.
-
이 문제에서는 start, end 사이 길이를 구하는 것이 중요합니다.
-
이렇게 start, end 두 포인터간 너비를 이용해 탐색하는 것은 슬라이딩 윈도우 알고리즘으로 분류됩니다.
-
조건에 중복값 허용이 안되므로 딕셔너리를 사용해 중복값을 제거 하겠습니다.
-
만약 end 값이 딕셔너리에 이미 있다면 기존 값을 삭제해주고 start 값을 1 증가시킵니다.
-
만약 end 값이 딕셔너리에 없다면 딕셔너리에 추가해주고 end 값을 1 증가시킵니다. 이때 최대 길이를 확인 후 갱신시킵니다.
-
코드로 구현 해봅시다.
문제해결 코드
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
seen = {}
maxLength = 0
start, end = 0, 0
while end < len(s):
# 딕셔너리에 end 값이 있는 경우: 제거, start 증가
if s[end] in seen:
del seen[s[start]]
start += 1
# 딕셔너리에 end 값이 없는 경우: 딕셔너리에 추가, end 증가
else:
seen[s[end]] = end
maxLength = max(maxLength, end - start + 1)
end += 1
return maxLength
- 시간복잡도는 배열 전체를 한 번만 탐색했으므로 O(n)입니다.
Software Developer