4 분 소요

Sliding Window

문제

문제 링크

Given a string s, find the length of the longest 

substring

 without repeating characters.

Example 1:

Input: s = “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3.

Example 2:

Input: s = “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: s = “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Constraints:

  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

스스로 고민

  • 문제가 잘 이해안갔다….
  • 그래서 다른 사람들 의견들을 봤는데 그런 의견들을 보고 도움이 많이 되었다.

The wording of the question was unclear for me. Example 3 does cover this where “wke” was the longest not “wkew”, but the wording of the question suggests that the substring can have multiple of the same character as long as it is not repeating.

“wkew” would pass because the substring does not have two w’s in a row.

Instead of:
Given a string, find the length of the longest substring without repeating characters.

I think this is a better wording:
Given a string, find the length of the longest substring without duplicate characters.

접근법

  • 어떤 문자열이 주어지고 중복이 없는 가장 긴 문자열의 길이를 리턴해주면 된다.
  • 투 포인터 패턴으로 쓰면 될거 같다. Slide Window랑 결국 둘이 비슷한거 같다.

의사코드

이전에 사용했던 코드를 재활용했다.

  • 배열의 길이를 n으로 선언
  • 중복 없는 문자열을 담을 sub_string 리스트 선언
  • 리스트 길이중 최대 값을 업데이트 하기위해 max 와 current 두 개 선언
  • 반복문을 통해 sub_string 리스트에 중복되는 게 없다면 해당 문자를 담아주고 current_length가 max_length 보다 크다면 값을 갱신
  • 만역 중복 문자열이 검사된다면 포함된 문자열의 앞부분은 날려주고 새로운 문자열을 담아준다
    • b,a,c,d,5 이렇게 담아 있는 상태에서 c가 들어온다면
    • 슬라이싱을 통해 d,5,c 로 진행하게 만든다.
    • 변경된 리스트의 길이로 업데이트

구현 코드

class Solution:

    def lengthOfLongestSubstring(self, s: str) -> int:

        n = len(s)

        sub_string = []

        max_length = 0

        current_length = 0

  

        for i in range(n):

            if s[i] not in sub_string:

                sub_string += s[i]

                current_length += 1

                while current_length > max_length:

                    max_length = current_length

  

            else:

                sub_string = sub_string[sub_string.index(s[i])+1:]

                sub_string += s[i]

                current_length = len(sub_string)

  

        return max_length

시간 복잡도와 공간 복잡도

  • 시간 복잡도: 중복 문자가 나타날 때마다 sub_string을 업데이트하므로, 최악의 경우에는 각 문자가 모두 한 번씩 처리된다. 이 때문에 내부 루프에서 sub_string의 모든 문자를 최대 한 번씩 검사하게 됩니다. 따라서 이 루프의 시간 복잡도는 O(n) 다.

  • 공간 복잡도: 이 코드의 공간 복잡도는 O(n) 다. sub_string 리스트는 문자열의 길이에 비례하여 공간을 차지한다. 최악의 경우, 모든 문자가 서로 다를 때 sub_string의 길이는 n이 되며, 따라서 O(n)의 공간을 차지한다. 그 외에 사용되는 변수들은 상수 개이므로 추가적인 공간을 할당하지 않는다.

회고 과정

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:

    def lengthOfLongestSubstring(self, s: str) -> int:

        n = len(s)

        char_index = {}  # 각 문자의 최신 인덱스를 저장하는 사전

        max_length = 0

        start_idx = 0  # 현재 부분 문자열의 시작 인덱스

  

        for i in range(n):

            if s[i] in char_index and char_index[s[i]] >= start_idx:

                # 이미 등장한 문자이고 현재 부분 문자열에 속할 경우

                start_idx = char_index[s[i]] + 1  # 시작 인덱스 갱신

  

            char_index[s[i]] = i  # 문자의 최신 인덱스 업데이트

            current_length = i - start_idx + 1

            max_length = max(max_length, current_length)

  

        return max_length

  1. 부분 문자열 관리 방식: 이전에 사용한 sub_string 리스트 대신, 각 문자의 최신 인덱스를 저장하는 사전 char_index를 사용한다. 이를 통해 중복 문자가 나타났을 때, 그 문자의 최신 인덱스를 확인하여 시작 인덱스를 갱신할 수 있다.

  2. 중복 검사 및 중복 문자 처리 방식: 중복 검사를 위해 사전 char_index를 사용하며, 중복 문자가 나타났을 때 해당 문자의 최신 인덱스가 현재 부분 문자열 내에 있는지 확인하여 시작 인덱스를 갱신한다. 이렇게 하면 문자를 제거하거나 리스트를 조작할 필요가 없어진다.

  3. 내부 루프 구조: 문자의 최신 인덱스를 업데이트하고, 현재 길이를 계산한 후 최대 길이를 업데이트하는 순서로 코드를 구성하여 올바른 타이밍에 최대 길이가 갱신되도록 한다.

  • 요약하자면 내가 했던 방식처럼 직접 리스트 내용을 관리하는 방법이 아닌 그냥 중복된 숫자가 나올 때마다 해당 문자열의 인덱스 값을 업데이트해주면서 그 값을 이용해 새로 시작되는 값을 기준으로 다시 카운트가 들어가고 여태까지 카운트 된 것 중에 max 값으로 리턴해주는 방식이다.
  • 위와 같은 논리로 문자를 직접 제거하거나 조작할 필요가 없어서 성능도 훨씬 더 좋다.

근데 문자를 직접 제거하거나 조작하면 왜 성능이 더 안 좋아질까?

  1. 복잡성 및 연산 비용: 데이터 구조의 조작 및 삭제 작업은 일반적으로 해당 데이터 구조의 내부 구성을 변경하거나 조정해야 합니다. 이에 따라 더 복잡한 계산이 필요하며, 이로 인해 연산 비용이 증가할 수 있다.

  2. 메모리 관리: 데이터 구조를 조작하거나 삭제할 때 메모리 할당 및 해제 작업이 필요하다. 이로 인해 메모리 사용량이 증가하고, 메모리 할당 및 해제 작업 자체도 일정한 시간 및 리소스를 필요로 하다.

  3. 데이터 이동: 데이터 구조 내에서 요소를 삭제하거나 이동하는 작업은 데이터의 물리적인 이동을 동반할 수 있다. 이는 데이터 복사 및 이동을 위한 시간과 리소스가 소요됨을 의미한다.

  4. 재할당 및 재구성: 데이터 구조의 크기를 동적으로 조정하는 작업은 재할당이나 재구성을 필요로 할 수 있다. 이는 새로운 메모리 공간을 확보하거나 기존 데이터를 새로운 구조로 이동하는 작업을 수반하므로 비용이 높아진다.

댓글남기기

참고