[4코3파] #298. Leetcode Sliding Window

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (298일차)
[4코1파] 2023.01.13~ (290일차)
[4코3파] 2023.10.01 ~ (28일차)

Today :

2023.10.28 [298일차]

Leetcode Sliding Window

[1] 121. Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

문제 설명

그날의 주식 가격이 담긴 배열 prices가 주어질 때, 해당 주식을 사고 팔아서 얻을 수 있는 가장 최대의 효율 profit을 return 함

문제 풀이 방법

Dynamic Programming 중 Kadane's Algorithm (카데인 알고리즘)으로 쉽게 풀 수 있다. 가장 싸게 살 수 있는 가격(minPrice)를 기억하고 현재 인덱스에서 팔았을때 profit과 지금까지의 최대 maxProfit을 비교하는 것이다.

내 코드

카데인 알고리즘을 사용하면 시간복잡도 O(n), 공간복잡도 O(1)

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        maxProfit = 0
        minPrice = prices[0]
        
        for price in prices:
            if price < minPrice:
                minPrice = price 
            maxProfit = max(maxProfit, price-minPrice)
                
        return maxProfit

---

[2] 3. Longest Substring Without Repeating Characters

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

문제 설명

주어진 문자열에서 반복 문자열이 없는 가장 큰 부분 문자열의 길이를 반환한다.

문제 풀이 방법

두개의 포인터로 문자열을 기준으로 왼쪽, 오른쪽 인덱스를 기억해가면서
문자열을 처음부터 끝까지 탐색하면서 문자열이 중복되지 않는 길이를 sliding window의 값으로 업데이트 한다.
문자열을 기억하기 위해 탐색하면서 나오는 문자열들은 따로 딕셔너리(해쉬맵)에 현재 문자열 key로, 현재 인덱스를 value로 저장한다.
탐색시 문자열이 기존에 있는 문자열이 다시 등장하고(해쉬맵 내에 값이 있다면), 현재의 문자 길이의 왼쪽의 인덱스보다 현재의 문자열이 나오는 인덱스가 더 크면 문자열 인덱스를 현재의 인덱스로 업데이트 한다.
문자열이 기존에 나왔던 문자열과 겹치지 않는다면, 현재의 이동하고 있던 인덱스와 현재 길이를 위해서 고정되어 있는 왼쪽 문자열의 인덱스와의 차이로 길이를 구한다.
구해진 길이는 기존의 계산하고 있었던 길이와의 대소관계를 비교해서 업데이트한다.

내 코드

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cntDict = {}
        l = 0
        longest = 0

        for r,c in enumerate(s):
            if c in cntDict and l<=cntDict[c]:
                l = cntDict[c]+1
            
            else:
                longest = max(longest, r-l+1)
            
            cntDict[c] = r
        
        return longest

---

[3]

https://leetcode.com/problems/longest-repeating-character-replacement/description/

문제 설명

문자열 s 와 정수 k가 주어질 때, 해당 문자열에서 정수 k 번 만큼 문자열을 치환해서 가장 긴 단일 문자열로만 이루어진 문자열을 만든다면(예 'aaa', 'bbb', 'cc') 만들 수 있는 최대 문자열의 길이를 return 한다.

문제 풀이 방법

주어진 문자열을 탐색하면서, two pointer를 사용해서 문자열의 왼쪽인덱스, 오른쪽인덱스를 0,0 으로 부터 초기화하고 시작하는데 탐색하면서 해당 단일 문자열들의 등장 횟수를 저장한다.
이 저장한 횟수가 가장 높은 문자열을 기준으로 다른 문자열을 치환하는 것이 효율적이므로,
문자열 기준 왼쪽과 오른쪽 인덱스의 차이인 현재까지의 문자열길이에서 가장 빈도수가 많이 나온 문자열의 차를 구하고, 이 차가 주어진 k보다 작다면 계속 오른쪽 인덱스를 늘려나가면서 중복문자열의 수를 늘려나가보고, 만약 이 차가 크다면 왼쪽 인덱스를 늘리고, 현재 왼쪽인덱스였던 문자열의 카운팅을 제거한다.
이런식으로 문자열을 전체적으로 탐색하면서, 중복 문자열의 최대 길이를 업데이트 한다.

내 코드

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        
        cnt = {}
        ans = 0

        l= 0
        maxf = 0

        for r in range(len(s)):
            cnt[s[r]] = 1 + cnt.get(s[r],0)
            maxf = max(maxf, cnt[s[r]])
            while (r-l+1) - maxf > k:
                cnt[s[l]] -= 1
                l +=1

            ans = max(ans, r-l+1)

        return ans

---