리트코드 3번 문제 : Longest Substring Without Repeating Characters

문제 설명 👨🏻‍💻

리트코드 3번 

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

 

입력받은 문자열 안에서 중복이 없는 가장 긴 부분문자열의 길이를 구하는 문제

 

(예시)

 

입력 = abcdddd

출력 = 3

 

---

코드 구현 👩🏻‍💻

• 알고리즘 종류: 투포인터, 슬라이딩 윈도우

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = set()
        left = 0
        result = 0

        for right in range(len(s)):
            while s[right] in window:
                window.remove(s[left])
                left += 1
            window.add(s[right])
            print(window)
            result = max(result, right - left + 1)
        return result

풀이 방법 👩🏻‍💻

손코딩 (발그림 지송합니다.)

투포인터, 슬라이딩 윈도우 기법을 이용해서 문제를 풀었고 
문자열의 시작부터 끝까지 포인터를 오른쪽으로 옮기면서 순회하며 
중복이 없는 문자열의 길이를 담는 변수로서 
set()으로 window라는 변수를 만들어 주었습니다.

입력 문자열 길이만큼 set으로 만들어 놓은 window에 right 포인터를 하나씩 옮겨가며 값을 저장하는데, 이미 윈도우에 s[right]의 중복값이 이미 담겨있을 경우 원래 있던 중복값을 지우고 left포인트를 오른쪽으로 옮겨서 순회하고 

이 과정에서 나온 가장 긴 문자열의 길이를 
result에 max함수를 사용해 저장해서 출력 했습니다.

 

이 문제를 풀면서 알게 된 것 👩🏻‍💻

set()의 자료구조

특정한 수가 한 번이라도 등장했는지를 검사할 땐 set()함수를 이용할 수 있다.

set()함수는 파이썬에서 집합을 표현할 때 사용하는 자료형이다.

따라서 단순히 특정한 데이터가 존재하는지 검사할 때에 매우 효과적이고 간결한 측면에서는 가장 우수하다.

set이 효율적인 자료구조이고 방문 복잡도가 O(1)이기 때문에 

그래프 bfs, dfs 알고리즘에서 visit을 확인할때 set을 사용하는 편이라고 한다.

딕셔너리와 셋은 둘다 둘 다 hash 구조이다.

dict는 key,value 형태로 저장이 되는 구조다.

📌 딕셔너리 = {키1: 값1, 키2: 값2}

 

set은 value(=key)로만 저장이 된다.

📌 세트 = {값1, 값2, 값3}

그래서 모양이 배열처럼 보이지만, key와 value가 하나로써 동일하게 설정 되어있는 구조다.

(값을 꺼낼 때 키로 꺼내든 밸류로 꺼내든 똑같은 값을 뱉는다.)

 

 set의 어떤 x라는 key(요소)에 접근할때 시간복잡도는 O(1) 이다.

 

참고: https://velog.io/@ekzm8523/set%EC%A7%91%ED%95%A9-%EC%95%8C%EA%B3%A0-%EC%93%B0%EC%9E%90

python set(집합) 알고 쓰자!

https://velog.io/@suasue/Python-%EB%94%95%EC%85%94%EB%84%88%EB%A6%AC-%EC%84%B8%ED%8A%B8-%EC%9E%90%EB%A3%8C%ED%98%95   :  딕셔너리, 세트 사용법

Python | 딕셔너리 & 세트 자료형

 

• 1차 시도, 최종 - set()을 사용만들어준 변수
  1. set을 이용한 window (set은 반복을 허용하지 않기 때문에 윈도우에 반복되지 않는 캐릭터들을 담을 수 있다)
  2. 반복되는 캐릭터를 제거해주기 위한 l(left) 포인터
  3. 서브 스트링 사이즈를 저장할 result
  입력배열 s를 오른쪽으로 한칸씩 이동하면서 순회left 포인트를 이동해주고 서브 스트링의 끝까지 right포인터를 add해주며 순회해준다.
• 이렇게 순회하면서 가장 길었던 윈도우 사이즈를 res값에 담아 리턴한다.
• 윈도우에 담긴 캐릭터가 이미 존재할 경우 이전에 등장했던 왼쪽의 캐릭터를 윈도우에서 제거해주고
• 전체 캐릭터를 한번씩 순회해야하기 때문에 시간복잡도는 O(N)