[leetcode] 2516. Take K of Each Character From Left and Right #2

안녕하세요! 어제 말씀드렸던대로 어제 풀었던 2516. Take K of Each Character From Left and Right 문제를 다시 풀어보겠습니다!

 

극악의 runtime!

• 참고: https://goodahn.tistory.com/250

 

1. 개선된 문제 풀이 - two pointer

끄아아악! 아쉽게도 더 나은 방법을 생각해내지 못했습니다. 이번에도 거침없이 leetcode의 풀이를 참고했습니다!

• 참고: https://leetcode.com/problems/take-k-of-each-character-from-left-and-right/editorial/#approach-2-sliding-window

leetcode의 풀이를 보니 two pointer 방식입니다.

two pointer 방식은 left 포인터와 right 포인터를 조절하면서 해답을 찾아가는 방법인데 이 문제에 어떻게 적용하는 걸까요?

 

거꾸로 생각하면 됐습니다.

문자열을 어떻게 자를지가 아니라 남겨도 되는 문자열이 무엇인지 찾는 것이죠!

발상의 전환!

 

1. two pointer 방식으로 남겨도 되는 문자열의 최대 길이를 구한 뒤,

2. 문자열의 길이에서 2의 길이를 빼면 최소 횟수를 구할 수 있습니다.

 

1. "a", "b", "c"가 문자열에 몇개 있는지 확인합니다.
2. 만약 하나라도 k번보다 적다면 -1을 반환합니다.
3. left=0, right=0, longest_removable_length=0, 으로 준비하고 left와 right가 문자열의 길이보다 작을 때까지 다음 과정을 반복합니다.
    3.1. 만약 right번째 문자를 제거하더라도 right번째 문자가 k개 이상 존재한다면
        - 1에서 확인한 문자의 개수에서 right번째 문자의 개수를 1 감소시킵니다.
        - right - left가 longest_removable_length보다 크면 longest_removable_length 값을 갱신합니다.
        - right를 1 증가시킵니다.
    3.2. 만약 right번째 문자를 제거하면 right번째 문자가 k개 미만 존재한다면
        - left가 right보다 작다면 1에서 확인한 문자의 개수에서 left번째 문자의 개수를 1 증가시킵니다.
        - left를 1 증가시킵니다.
        - 만약 left가 right보다 커졌으면 right의 값을 left의 값으로 설정합니다.
4. 문자열의 길이에서 longest_removable_length를 뺀 값을 반환합니다.

 

위 방법의 시간복잡도는 O(n)으로 이전 방법인 O(n log n)보다 훨씬 빠릅니다!

 

 

71%로 상승한 runtime 효율!

 

P.S.

이쯤 되면 two pointer 방식에는 익숙해져야 할텐데 아직도 응용력이 부족한 것 같습니다 ㅜㅠ

더욱 정진해야겠네요!

 

+ 코드

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        freq = [0] * 3
        for c in s:
            freq[ord(c)-ord("a")] += 1

        for f in freq:
            if f < k:
                return -1
        
        longest_removable_length = 0
        left, right = 0, 0
        while left < len(s) and right < len(s):
            if freq[ord(s[right])-ord("a")] > k:
                freq[ord(s[right])-ord("a")] -= 1
                right += 1
                longest_removable_length = max(longest_removable_length, right-left)
            else:
            	if left < right:
                    freq[ord(s[left])-ord("a")] += 1
                left += 1
                if left > right:
                    right = left
        return len(s) - longest_removable_length