리트코드에서 새로운문제를 가져왓습니다.
리트코드는 근데 왜 난이도순으로 번호가 안매겨져있는지.......휴..
✏️ 오늘 푼 문제
Longest Substring Without Repeating Characters
✏️ 필요 사전 지식
- 해시맵
- 슬라이딩 윈도우
해시맵
- 단어장과 비슷한 개념을 가집니다. 단어와 의미를 key와 value로 짝지어 표현한 형태입니다.
- 해당 문제에서는 문자열에서 각 문자가 어디에 있는지 기록하기 위해 사용할 것입니다!
슬라이딩 윈도우
- 창문이 문자열을 훑으면서 움직이는 형태입니다.
- 예를들어 abcabcbb라는 문자열아 있으면 첫 창문엔 a가 있고, 오른쪽으로 움직이면 창문에 b가 들어가게 됩니다. (왼쪽으로 움직이는 것도 가능)
- 해당 문제에서는 창문을 계속 오른쪽으로 움직이면서 최대 부분 문자열 길이를 업데이트하는데 쓰입니다.
✏️ 접근 방법
- 문자열을 순회하면서 각 문자를 해시맵에 저장
- 만약 이미 등장한 문자가 또 등장했다면 이전 등장 위치를 갱신
- 슬라이딩 윈도우를 사용해 가장 긴 부분의 문자열 길이를 유지하면서 문자열 순회
✏️ 답안 코드
def lengthOfLongestSubstring(self, s: str) -> int:
char_index = {} # 문자와 해당 문자의 인덱스 값을 저장할 해시맵
max_len = 0 # 최대 부분 문자열 길이
start = 0 # 슬라이딩 윈도우의 시작 인덱스
for end in range(len(s)):
# 현재 문자가 이미 딕셔너리에 있고 슬라이딩 윈도우 값보다 크거나 같을 때
# 즉, 중복된 문자열이 등장했을 때
if s[end] in char_index and char_index[s[end]] >= start:
# 슬.윈 시작 위치를 갱신
start = char_index[s[end]] + 1
# 현재 문자의 인덱스를 딕셔너리에 업데이트
char_index[s[end]] = i
# 현재 윈도우 길이를 계산하여 최대 길이와 비교
max_len = max(max_len, end-start+1)
return max_lenfor문, 특히 char_index[s[i]]를 작성해야한다는 것을 나혼자선 절대 모를것같다. char_index[i] 정도로 짜고 왜틀렷지 하고잇을듯,, 그래서 추가설명!
For문 부분 예시
🪄 주어진 문자열: abcabcbb
-
초기에 start는 0이며, char_index는 빈 딕셔너리입니다.
-
end == 0일때, s[0] = a이므로 딕셔너리에 a 추가. start(윈도우의 길이) = 1
-
end == 1일때, s[1] = b이므로 딕셔너리에 b 추가. start = 2
-
end == 2일때, s[2] = c이므로 딕셔너리에 c 추가. start = 3
-
end == 3일때, s[3] = a로 중복되는 문자이므로 추가X. 기존 a의 위치였던 0에 1을 더해 b부터 문자열을 다시 탐색
-
a의 인덱스 번호를 3으로 갱신
-
길이 비교 후 다시 for문 실행
💡 char_index가 완성되는 구체적인 과정
문자열: a b c a b c b b
인덱스: 0 1 2 3 4 5 6 7
# 초기 상태
char_index = {}
# end = 0
s[0] = 'a'
char_index = {'a': 0}
# end = 1
s[1] = 'b'
char_index = {'a': 0, 'b': 1}
# end = 2
s[2] = 'c'
char_index = {'a': 0, 'b': 1, 'c': 2}
# end = 3
s[3] = 'a'
char_index = {'a': 3, 'b': 1, 'c': 2}
# end = 4
s[4] = 'b'
char_index = {'a': 3, 'b': 4, 'c': 2}
# end = 5
s[5] = 'c'
char_index = {'a': 3, 'b': 4, 'c': 5}
# end = 6
s[6] = 'b'
char_index = {'a': 3, 'b': 6, 'c': 5}
# end = 7
s[7] = 'b'
char_index = {'a': 3, 'b': 7, 'c': 5}끝
