[파이썬/Python] Leet Code 3(Medium): Longest Substring Without Repeating Characters

숨·2025년 8월 22일

코테

알고리즘 문제 풀이

목록 보기

117/128

📌 문제 : Leet Code 3

📌 문제 탐색하기

s : 입력되는 문자열 ( $0 ≤ s.length ≤ 5 * 10^4$ )

문제 풀이

문자열 s에서 중복 글자가 없는 가장 긴 substring의 길이를 찾는 문제이다.

문자를 하나씩 접근하면서 임시 리스트에 중복 문자가 있는지 여부를 확인한다.
임시 리스트에 중복 문자가 있다면 해당 문자의 다음 부분부터 임시 리스트에 저장한다.
→ 즉, 중복 문자만 빼고 저장하는 것이다.

s가 끝날 때까지 이를 반복하면서 문자열을 찾고 최대 길이를 갱신한다.

가능한 시간복잡도

문자열 확인 → $O(s)$
리스트에 있는지 확인 → $O(s)$

최종 시간복잡도
최악일 때 $O(s^2) = O(25 * 10^8)$ 이 되는데 이는 시간 초과가 일어날 위험이 크다.
→ 다른 풀이 방식 필요하나 떠오르지 않음

알고리즘 선택

문자열 돌면서 확인

📌 코드 설계하기

임시 리스트, 최대 길이 초기화
문자열 하나씩 확인
중복 문자 만났을 때 중복이 나온 위치 다음부터 남긴다
길이 더 길면 갱신

📌 시도 회차 수정 사항

1회차

s consists of English letters, digits, symbols and spaces.
무조건 영문으로 된 문자열이 입력될 것이란 생각으로 풀었다. 위와 같은 제약사항이 고려하지 않아 다른 입력이 들어왔을 때 제대로 동작하지 않았던 것이라 생각했다.

		# 임시 리스트, 정답 리스트 정의
        li_temp = []
        li_answer = []

        # 문자열 하나씩 확인
        for i in range(len(s)):
            # 임시 리스트에 해당 문자 없으면 추가
            if s[i] not in li_temp:       
                li_temp.append(s[i])
                li_answer = li_temp


            # 있으면 임시 리스트와 저장 리스트 길이 비교
            else:
                # 임시 리스트가 더 길면 정답 리스트에 갱신 후 초기화
                if len(li_temp) >= len(li_answer):
                    li_answer = li_temp

수정 전엔 위와 같이 임시 리스트, 정답 리스트를 정의해 일정 조건에 맞았을 때 임시 리스트를 정답 리스트에 복사하는 형식으로 구현했는데 파이썬의 리스트 참조 문제와 임시 리스트 초기화하는 부분에 문제가 생겼던 것 같다.
또한 입력이 한자리일 때는 임시 리스트에 추가되지 않아서 원하는 대로 수행되지 않았다.
해결
- 정답 리스트를 따로 정의하지 않고 최대 길이만 저장하는 방식으로 변경했다.
- 중복 문자를 만났을 때 초기화하는 것이 아닌, 임시 리스트에 먼저 들어가 있었던 중복 문자의 그 다음 위치 문자부터 임시 리스트에 남기도록 했다.

📌 정답 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 임시 리스트, 최대 길이 초기화
        li_temp = []
        max_len = 0

        # 문자열 하나씩 확인
        for char in s:
            # 중복 문자 만났을 때
            if char in li_temp:
                # 중복이 나온 위치 다음부터 남긴다
                idx = li_temp.index(char)
                li_temp = li_temp[idx+1:]

            li_temp.append(char)

            # 길이 더 길면 갱신
            if len(li_temp) > max_len:
                max_len = len(li_temp)

        return max_len

결과

👍 다른 풀이 1 - 슬라이딩 윈도우

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
		# 문자가 마지막으로 등장한 인덱스를 기록하는 딕셔너리
        last_seen = {}
        # 윈도우의 시작점(left), 최대 길이(max_len) 초기화
        left = 0
        max_len = 0

        # 문자열을 right(끝) 인덱스 기준으로 한 글자씩 확인
        for right, char in enumerate(s):
            # 만약 현재 글자가 이미 윈도우 내에 있다면(left보다 같거나 크면, 즉 겹침)
            if char in last_seen and last_seen[char] >= left:
                # 윈도우의 시작(left)을 중복 문자 다음으로 점프
                left = last_seen[char] + 1

            # 현재 문자의 인덱스를 기록
            last_seen[char] = right

            # 현재 윈도우 크기로 최대값 갱신
            max_len = max(max_len, right - left + 1)

        return max_len

진행
- last_seen에 각 문자마다 가장 최근 위치를 기록
- 현재 윈도우인 [left, right] 구간에 중복이 있다면 left를 중복 다음 위치로 점프
장점
- 시간 복잡도 : $O(N)$
- 중복 문자 있으면 left로 바로 점프해서 투 포인터보다 빠름
단점
- 인덱스 기록 필요해 메모리가 더 필요
결과

📖 슬라이딩 윈도우 (Sliding Window)

고정 사이즈의 윈도우가 이동하면서 윈도우 내의 데이터를 활용해 문제 풀이하는 알고리즘

<네트워크 용어> 2개의 네트워크 호스트 간 패킷 흐름 제어 위한 방법

투 포인터와 비슷

차이

투 포인터 : 윈도우 사이즈가 가변적이며 좌우 포인터가 자유롭게 이동 가능하고 주로 정렬된 배열을 대상

슬라이딩 윈도우 : 고정 사이즈 윈도우 활용하며 좌 또는 우 단방향으로 이동하고 정렬 여부 관계 없이 활용

👍 다른 풀이 2 - 투 포인터 활용

class Solution:
    def lengthOfLongestSubstring(s: str) -> int:
    	# 현재 윈도우 내의 문자를 관리하는 집합
    	chars = set()
    	n = len(s)
    	left = right = 0
    	max_len = 0

    	# right(끝)를 늘려가면서 확인
    	while right < n:
      	  # 윈도우에 중복 없으면 추가하고 길이 갱신
        	if s[right] not in chars:
            	chars.add(s[right])
            	max_len = max(max_len, right - left + 1)
            	right += 1
        	else:
            	# 중복이면 left를 늘려가서 중복이 해결될 때까지 계속 제거
        	    chars.remove(s[left])
    	        left += 1
	
	    return max_len

진행
- right를 한 칸씩 늘리면서 중복 없을 때까지 집합에 추가
- 중복 나올 때마다 left 한 칸씩 움직여 집합에서 제거
- [left, right-1]이 중복 없는 윈도우
장점
- 시간 복잡도 : $O(N)$
- 코드 간결하고 직관적
단점
- left를 여러 번 이동 → 아주 긴 입력엔 느릴 수 있음
결과

✏️ 회고

이번 문제는 알고리즘 공부의 중요성을 느끼게 해준 문제였다. 문제 푸는데에만 집중하다보니 관련 공부를 따로 하지 않아서 효율적인 풀이 방법은 떠올리지 못했다. 입력이 더 컸다면 내 풀이로는 시간 초과가 났을 것 같다. 하루에 한 주제씩이라도 알고리즘 공부 시간을 가져야겠다.