책 리뷰/파이썬 알고리즘 인터뷰

11장. 해시 테이블(5) - 예제(중복 문자 없는 가장 긴 부분 문자열)

조조링 2024. 11. 9. 12:21
728x90
반응형

 

중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴한다.
입력: "abcabcbb"
출력: 3
입력: "pwwkew"
출력: 3

 

 

풀이1. 슬라이딩 윈도우와 투 포인터로 사이즈 조절

이 문제는 "슬라이딩 윈도우"와 "두 포인터" 기법을 사용하여 해결할 수 있다.
슬라이딩 윈도우는 문자열의 특정 구간을 반복적으로 이동하면서 중복 없이 가장 긴 구간을 찾는 방법이다.

그림1. 부분 문자열을 찾는 투 포인터 풀이

 

1. 슬라이딩 윈도우와 두 포인터의 역할

  • 윈도우: 문자열에서 중복 없는 구간을 나타낸다.
  • 두 포인터 (start와 index): start는 현재 윈도우의 시작 위치, index는 현재 문자의 위치를 나타낸다.

이 방법은 두 포인터를 이용해 윈도우의 크기를 조절하며 중복이 생길 때마다 시작 위치를 업데이트하는 방식으로 작동한다.

 

예시를 통해 이해하기

입력: "abcabcbb"

  1. 문자열 "a"는 중복이 없으므로 윈도우 길이는 1이 된다.
  2. 다음 문자 "b"도 중복이 없으므로 "ab"로 확장, 길이는 2이다.
  3. "c"를 추가해 "abc"로 확장하여 길이는 3이 된다.
  4. 이후 "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"일 때를 예로 들어보자.

  1. index = 0, char = 'a':
    • 윈도우에 중복이 없으므로, max_length를 1로 갱신
    • used에 'a': 0을 저장
  2. index = 1, char = 'b':
    • 중복이 없으므로 max_length를 2로 갱신
    • used에 'b': 1을 저장
  3. index = 2, char = 'c':
    • 중복이 없으므로 max_length를 3으로 갱신
    • used에 'c': 2를 저장
  4. index = 3, char = 'a':
    • 'a'가 이미 used에 있고, start는 0이므로 중복이 발생
    • start를 1로 갱신하여 "bca"로 윈도우를 재설정 =>  max_length는 여전히 3
  5. 이후에도 동일한 방식으로 윈도우를 조정하며 최대 길이를 유지

결과적으로, 가장 긴 중복 없는 부분 문자열의 길이는 3이 된다.

 

요약

  • 슬라이딩 윈도우와 두 포인터 기법으로 문자열을 순회하며 중복을 확인한다.
  • 중복이 발생할 때마다 윈도우 시작 위치를 업데이트하여 최대 길이를 찾는다.
  • 해시 테이블(used)을 이용해 각 문자의 위치를 기록하여 효율적으로 중복을 확인할 수 있다.

이 방법은 O(n) 시간 복잡도로 매우 효율적이다.

728x90
반응형