[Algorithm][투 포인터] LeetCode 3 - Longest Substring Without Repeating Characters

알고리즘 분류

 Two Pointer

 

시간 복잡도

 \( O(N) \)

 

문제 링크

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

 

관련 글

[Algorithm 문제 풀이/백준] - [Algorithm][투 포인터] 백준 1806 - 부분합

---

 이번 문제의 알고리즘 종류는 투 포인터입니다. 투 포인터는 이전 글에서도 다른 문제로 한번 접했습니다. 개념도 단순하고 코드도 상당히 짧지만, 알고리즘을 모른다면 쉽게 풀지 못하는 문제이기도 합니다.

 

 해당 문제는 서로 다른 부분 문자열 중 가장 길이가 긴 것을 찾아야 합니다. 만약 이것을 이중 for문을 이용한다면 당연스럽게도 시간 복잡도는  \( O(N^2) \) 이므로 상당히 비효율적인 방법이라고 할 수 있습니다. 왜냐하면 중복된 부분 문자열이 상당히 많기 때문입니다. 이러한 중복 문자열은 투 포인터를 이용하여 제거할 수 있습니다.

 

 start와 end 변수를 0으로 초기화하고 문제에서 주어진 문자열의 index를 순차적으로 탐색합니다. s[start:end]은 현재 시작과 끝을 나타내는 부분 문자열을 뜻합니다.

 

    1. end가 가리키는 문자열이 현재 부분 문자열에 포함이 안되면 end의 값을 1 늘려준다.

    2. 포함을 하고있다면 문제의 조건을 만족하지 않으므로 start 값을 1 늘려준다.

    3. 현재 end의 값이 마지막 문자열을 넘었다면 종료한다.

 

 위의 순서대로 반복문을 계속 돌리면서 문제의 조건을 만족시킬 때마다 최대 길이를 업데이트해줍니다. 그래서 최종적으로 반복문이 끝나면 문제의 조건을 만족하는 모든 경우의 수를 알아본 것입니다. 아래의 과정을 참고하면 이해하기 쉽습니다.

 

 이러한 투 포인터 알고리즘은 문자열을 가리키는 start와 end가 각각 최대 N번 움직일 수 있습니다. 그래서 각 포인터마다 \( O(N) \)의 시간 복잡도가 발생하고 모두 합쳐 최종적으로도 \( O(N) \)의 시간 복잡도를 가집니다.

 

 \( O(N) \)의 시간 내에서도 end가 가리키는 문자열이 현재 부분 문자열에 포함되는지 여부를 어떻게 구현하느냐에 따라 미세하게 시간 차이가 날 수 있습니다. 만약 부분 문자열 자체를 s[start : end] 로써 문자열 형태로 저장한다면 매번 부분 문자열 길이만큼 탐색을 해서 포함 여부를 알아야 합니다. 그래서 자칫 잘못하면 상당한 시간이 걸릴 수 있습니다. 이 때는 python dictionary를 이용하여 부분 문자열이 포함된 문자들을 key 값으로 저장합니다. 그러면 특정 문자열이 부분 문자열에 포함되는지 여부를 key값 존재를 통해 알아내므로 매번 \( O(1) \)로 위의 방법과 비교해 상당히 짧은 시간에 해결이 가능합니다.

 

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start, end, res = 0, 0, 0
        dic = {}
        
        if len(s) == 0 : return 0
        
        while True:
            if s[end] not in dic:
                dic[s[end]] = 1
                end = end + 1
                res = max(res, end - start)
            else:
                del dic[s[start]]
                start = start +1
        
            if end == len(s):
                break
                
        return res