[1스4코2파] #130. LeetCode Algorithm Day 6 (3. Longest Substring Without Repeating Characters Medium, 567. Permutation in String)

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코2파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (130일차)
[4코1파] 2023.01.13~ (121일차)
[1스4코1파] 2023.04.12~ (32일차)
[1스4코2파] 2023.05.03 ~ (11일차)

Today :

2023.05.12 [130일차]

LeetCode Algorithm Day 6
3. Longest Substring Without Repeating Characters

• https://leetcode.com/problems/longest-substring-without-repeating-characters/?envType=study-plan&id=algorithm-i

567. Permutation in String

• https://leetcode.com/problems/permutation-in-string/?envType=study-plan&id=algorithm-i

문제 1

[3] Longest Substring Without Repeating Characters

내 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str):
        answer, start = 0,0
        tmpDict = {}

        for end, string in enumerate(s):
            if string in tmpDict and start<=tmpDict[string]:
                start = tmpDict[string]+1

            else:
                answer= max(answer, end-start+1)
            tmpDict[string] = end

        return answer

문제 풀이 방법

고정 사이즈의 window를 이동하면서, window 내에 있는 원소의 데이터를 이용해 문제를 풀이하는 'Sliding Window' 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘으로 푸는 문제다.

인덱스 start, end를 (window 사이즈) 주어진 문자열에서 중복된 문자가 존재한다면 그 인덱스부터 중복된 문자를 찾는 과정을 반복하면서 찾음.

증빙

---

문제 2

[567] Permutation in String
https://leetcode.com/problems/permutation-in-string/?envType=study-plan&id=algorithm-i

내 코드

from collections import Counter

s1, s2 = 'abc', 'bbbca'
answer = False
s1Cnt = Counter(s1)
for i in range(len(s2)):
    subword = s2[i:i+len(s1)]
    s2Cnt = Counter(subword)
    if s1Cnt == s2Cnt:
        answer = True
        break
        
answer

문제 풀이 방법

프로그래머스에서 유사한 문제를 풀어봐서 수월하게 풀었음
collections의 Counter를 이용해서 주어진 s1 문자열의 각 문자 element 들의 counting 하고,
뒤에 s2를 for 문으로 순회하면서, 이때 s2 인덱스를 0부터 s2 끝까지 돌되, s1의 길이만큼 슬라이싱하면서 이동한다.
이때 슬라이싱하면서 구성된 s2의 subword의 문자열의 element들의 counting해서 같으면 부분 문자열로 인식함

증빙

여담

오늘은 토요일 후다닥 끝내고 명량핫도그먹어야됨 냠