[Leetcode] 3. Longest Substring Without Repeating Characters

Coding Test

[Leetcode] 3. Longest Substring Without Repeating Characters

동만쓰 2022. 5. 21. 02:14

Solution

class Solution(object):
    def lengthOfLongestSubstring(self, s : str)-> int:
      used={}
      max_length = start= 0

      for index,char in enumerate(s):

        if char in used and start <= used[char]:
          start=used[char]+1
        else:
          max_length = max(max_length,index-start+1)

        used[char] = index
        
      return max_length

포인터 index,start는 문자열의 가장 왼쪽에서 시작합니다.

index 포인터는 오른쪽으로 한칸씩 이동합니다.

만약 이미 등장한 문자라면 used에 있을 것이고, 이 경우 첫 번째 포인터인 start를 used[char]+1 위치로 갱신시킵니다.

str="abcabcbb"
a=Solution()
a.lengthOfLongestSubstring(str)

다음과 같이 함수를 실행시키고 start와 index가 매 loop 마다 어떤 값을 출력하는지 확인해 보겠습니다.

start: 0 index: 0
start: 0 index: 1
start: 0 index: 2
start: 1 index: 3
start: 2 index: 4
start: 3 index: 5
start: 5 index: 6
start: 7 index: 7

used[char]에 같은 문자가 여러개 저장되어 있는 경우 가장 나중에 들어간 문자를 기준으로 가져오게 됩니다.

used[char]는 현재 문자를 키로 하는 해시 테이블이며, 여기에는 현재 위치를 값으로 삽입합니다.

Enumerate

data = enumerate((1, 2, 3))
print(data, type(data))

for i, value in data:
    print(i, ":", value)
print()

enumerate는 리스트의 순서와 값을 전달합니다.

for문과 함께 자주 쓰이며 순서가 있는 자료형을 다룰 때 유용하게 쓰입니다.

동시 할당

파이썬에서는 동시 할당을 할 때 =를 사용합니다. (, 아님)

해당 문제에서 사용한 방법은 슬라이딩 윈도우 알고리즘과 투포인터 입니다. 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 유용한 알고리즘 입니다.

이 두 알고리즘은 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다는 공통점이 있습니다.

투포인터

투 포인터는 연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘입니다. 여기서 중요한 것은 "연속되고 가변적인"입니다. 값이 연속된다는 말은 정렬을 뜻하는 것일 수도 있으니 부분 배열로 작성하였습니다. 만약 문제에서 주어진 배열이 연속된 부분 배열을 통하여 문제를 해결하라는 것이 아니면 (예를 들어, 연속적이지 않은 arr[0]과 arr[3]을 부분 배열로 하는 문제) 투 포인터 알고리즘을 사용할 수 없습니다. 이런 상황에서는 주어진 배열을 그대로 이용하여 문제를 해결하거나 배열의 인덱스와 값을 함께 list에 저장한 후 오름차순, 혹은 내림차순 정렬을 통하여 연속성을 추가해준 다음에 투 포인터 알고리즘을 사용하여야 합니다.

즉, 투 포인터 알고리즘에서는 대게 두 개의 유형이 존재합니다.

1) 2개의 포인터 변수 시작점이 배열의 시작점인 경우.

2) 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점(arr.length-1)에 위치한 경우

투 포인터 알고리즘을 해결하기 위해서는 보통 배열을 가리키는 2개의 포인터 변수를 많이 사용하는데 바로 Left, Right입니다. (취향 차이지만 Statr, End로 해도 됩니다.) 또 문제마다 다르겠지만 Target 변수(목표로 하는 값)도 사용됩니다. 이 포인터 변수들을 이동해가면서 부분 배열을 구하고 원하는 값을 찾으면 됩니다.

여기서 중요한 것은 두 포인터의 의미입니다. 이 두 포인터는 [Left, Right)을 의미합니다. (arr배열이 있으면 부분 배열은 arr[Left]부터 arr[Right-1]까지의 부분 배열을 뜻합니다.)

만약, 정수로 이루어진 배열에서 연속된 부분 배열의 합이 특정 값(Target)을 이루는 부분 배열의 개수를 구하는 문제가 있다고 가정했을 때, 두 포인터 변수의 이동 조건은 다음과 같습니다.

(1) 부분 배열의 합이 Target 값보다 크거나 같으면 Left = Left + 1 해줍니다. (부분 배열의 길이를 줄여 합을 빼준다. )

if(sum >= Target) Left++;

(2) 부분 배열의 합이 Target 값보다 작으면 Right = Right + 1 해줍니다. (부분 배열의 길이를 늘려 합을 더한다.)

if(sum < Target) Right++;

(3) 부분 배열의 합이 Target 값과 같다면 결과 값을 +1 해줍니다.

if( sum == Target) count++;

Sliding Window

슬라이딩 윈도우 알고리즘은 연속되는 투 포인터와 유사하게 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘이지만 부분 배열의 길이(크기)가 고정적입니다. 어떤 창문을 왼쪽부터 오른쪽으로 밀어 오면서 창문 안에 있는 값들을 부분 배열이라고 생각하면 될 것 같습니다.

또 다른 차이점은 투 포인터 알고리즘은 부분 배열의 길이가 가변적이기 때문에 부분 배열의 구간을 정할 2개의 포인터 변수가 필요한 반면, 슬라이딩 윈도우 알고리즘은 부분 배열의 길이를 고정적으로 잡기 때문에 포인터 변수가 2개일 필요가 없습니다. 즉, 고정적인 부분 배열의 크기를 나타내는 변수가 있다면 포인터 하나만 있어도 부분 배열의 크기를 알고 있기 때문에 각 배열의 끝을 어딘지 알 수 있습니다.

출처: https://bbangson.tistory.com/72 [뺑슨 개발 블로그]