책 리뷰/파이썬 알고리즘 인터뷰
11장. 해시 테이블(5) - 예제(중복 문자 없는 가장 긴 부분 문자열)
조조링
2024. 11. 9. 12:21
728x90
반응형
중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴한다.
입력: "abcabcbb"
출력: 3
입력: "pwwkew"
출력: 3
풀이1. 슬라이딩 윈도우와 투 포인터로 사이즈 조절
이 문제는 "슬라이딩 윈도우"와 "두 포인터" 기법을 사용하여 해결할 수 있다.
슬라이딩 윈도우는 문자열의 특정 구간을 반복적으로 이동하면서 중복 없이 가장 긴 구간을 찾는 방법이다.
1. 슬라이딩 윈도우와 두 포인터의 역할
- 윈도우: 문자열에서 중복 없는 구간을 나타낸다.
- 두 포인터 (start와 index): start는 현재 윈도우의 시작 위치, index는 현재 문자의 위치를 나타낸다.
이 방법은 두 포인터를 이용해 윈도우의 크기를 조절하며 중복이 생길 때마다 시작 위치를 업데이트하는 방식으로 작동한다.
예시를 통해 이해하기
입력: "abcabcbb"
- 문자열 "a"는 중복이 없으므로 윈도우 길이는 1이 된다.
- 다음 문자 "b"도 중복이 없으므로 "ab"로 확장, 길이는 2이다.
- "c"를 추가해 "abc"로 확장하여 길이는 3이 된다.
- 이후 "a"가 다시 등장하면, "abc"에 포함되어 있으므로 중복이 생긴다. 이때 start 포인터를 "b"의 위치로 옮겨 "bca"로 윈도우를 재설정한다.
이 과정을 반복하면 최대 길이인 3을 얻을 수 있다.
[전체 코드]
def lengthOfLongestSubstring(self, s: str) -> int:
used = {} # 문자와 해당 문자의 인덱스를 저장하는 해시 테이블
max_length = 0 # 최대 부분 문자열 길이를 저장
start = 0 # 현재 윈도우의 시작 위치
for index, char in enumerate(s): # 문자열을 순회하며 문자와 인덱스를 가져옴
# 중복된 문자이고, start가 중복 문자의 위치를 넘어가지 않았다면 윈도우 시작 위치를 갱신
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
코드 동작 예시
입력 문자열이 "abcabcbb"일 때를 예로 들어보자.
- index = 0, char = 'a':
- 윈도우에 중복이 없으므로, max_length를 1로 갱신
- used에 'a': 0을 저장
- index = 1, char = 'b':
- 중복이 없으므로 max_length를 2로 갱신
- used에 'b': 1을 저장
- index = 2, char = 'c':
- 중복이 없으므로 max_length를 3으로 갱신
- used에 'c': 2를 저장
- index = 3, char = 'a':
- 'a'가 이미 used에 있고, start는 0이므로 중복이 발생
- start를 1로 갱신하여 "bca"로 윈도우를 재설정 => max_length는 여전히 3
- 이후에도 동일한 방식으로 윈도우를 조정하며 최대 길이를 유지
결과적으로, 가장 긴 중복 없는 부분 문자열의 길이는 3이 된다.
요약
- 슬라이딩 윈도우와 두 포인터 기법으로 문자열을 순회하며 중복을 확인한다.
- 중복이 발생할 때마다 윈도우 시작 위치를 업데이트하여 최대 길이를 찾는다.
- 해시 테이블(used)을 이용해 각 문자의 위치를 기록하여 효율적으로 중복을 확인할 수 있다.
이 방법은 O(n) 시간 복잡도로 매우 효율적이다.
728x90
반응형