출처
: LeetCode
문제
Given a string s, find the length of the longest substring without repeating characters.
(생략)
나의 풀이(시도)
1
2
3
4
5
6
# 반복되는 문자 아니면 여기에 추가
temp_corpus = input_str[0]
idx_str = 1
while(True):
temp_pick_char = input_str[idx_str]
if (temp_pick_char == input_str[idx_str - 1])
계속 여기서 몇시간 고민하다가 결국 포기했다.
뭔가 이중 반복문이더라도 효율적인 게 있을 거라 생각했다.
다른 사람들의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def lengthOfLongestSubstring(self, input_str: str) -> int:
charSet = set()
l = 0
result = 0
for idx_chr in range(len(input_str)):
while (input_str[idx_chr] in charSet):
charSet.remove(input_str[l])
l += 1
charSet.add(input_str[idx_chr])
result = max(result, (idx_chr - l + 1))
return result
이 코드는 아래의 유튜브 채널 영상에 나온 코드를
내 임의대로 변수명을 바꿔본 것이다.
Longest Substring Without Repeating Characters - Leetcode 3 - Python
코드 한 줄 한 줄이 다 주옥같지만
그중에서 가장 핵심이 되는 코드를 꼽아보자면
1
2
3
while (input_str[idx_chr] in charSet):
charSet.remove(input_str[l])
l += 1
이 부분이 될 것 같다.
이 코드를 중심으로 구현된 기법에 대해 명칭도 있는데,
슬라이딩 윈도우(Sliding Window)라고 불린다고 한다.
간단히 설명하면, 예를 들어서
문자열의 연속 부분 문자열에 네모로 표시한 뒤에
그 네모를 앞뒤로 문자 한 개씩 이동하려는 아이디어이다.
위의 링크 속 유튜브 영상을 보면
그 아이디어에 대한 설명이 나와있다.