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

안녕하세요. 오늘은 leetcode의 2516. Take K of Each Character From Left and Right 문제를 풀어봤습니다.

• https://leetcode.com/problems/take-k-of-each-character-from-left-and-right/description/

1. 문제

이 문제에서는 "a", "b", "c"로만 이뤄진 문자열과 숫자 k가 주어집니다.

 

한번에 왼쪽 끝 혹은 오른쪽  끝에 있는 문자를 하나씩 잘라낼 수 있을 때, "a", "b", "c"를 각각 최소 k개 씩 뽑을 수 있는 최소한의 횟수를 구해야 합니다.

• 만약 주어진 문자열이 조건을 만족하지 않는다면 -1을 반환합니다.

 

예시)

• "abcccba", k=2
• 왼쪽에서 3개 오른쪽에서 3개, 총 6번 자르는 자르는 것이 최소한의 횟수입니다.

예시 문제에 대한 해답

 

2. 풀이

2.1. brute force

역시 가장 간단한 방법은 모든 경우의 수를 전부 따져보는 것입니다.

 

이 문제는 어떻게 모든 경우의 수를 찾을 수 있을까요? 생각보다 단순합니다.

n에 3 * k부터 문자열의 길이까지 대입하면서 다음 과정을 반복하면 됩니다.

• "a", "b", "c"가 각각 최소 k개씩은 존재해야 하므로 최소한 3 * k 번은 잘라야 하니 3 * k부터 시작합니다.

1. 문자열을 왼쪽에서 n개, 오른쪽에서 0개 자르고 "a", "b", "c"가 최소 k개씩 존재하는지 확인합니다.

2. 문자열을 왼쪽에서 n-1개, 오른쪽에서 1개 자르고 "a", "b", "c"가 최소 k개씩 존재하는지 확인합니다.

...

n. 문자열을 왼쪽에서 0개, 오른쪽에서 n개 자르고 "a", "b", "c"가 최소 k개씩 존재하는지 확인합니다.

 

 

하지만 이 방법의 시간복잡도는 O(n^2)으로 문자열의 길이가 최대 10^5까지 늘어날 수 있는 이 문제에서는 사용할 수 없습니다.

2.2. binary search

저에게 brute force 다음으로 만만한 방법이 binary search인 것 같습니다.

binary search를 적용하는 방법은 간단했습니다.

 

3 * k 부터 문자열의 길이까지 점진적으로 증가시키는 대신 3 * k와 문자열의 길이 사이에서 이진 탐색을 진행하는 것이죠.

- mid 횟수가 조건을 만족했을 때는 3 * k와 mid 사이에서 찾기

mid 횟수만에 조건을 만족했을 때 다음 탐색 영역

- mid 횟수가 조건을 만족하지 않을 때는 mid와 문자열의 길이에서 찾기

mid 횟수가 조건을 만족하지 않을 때 다음 탐색 영역

 

이렇게 이진 탐색으로 문제를 풀 수 있었습니다.

하지만 runtime 효율성이 극악입니다... 다음에는 이걸 개선해봐야겠습니다!

풀었지만... runtime이... ㅜ

+ 코드

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        if k == 0:
            return 0
        if k > len(s) // 3:
            return -1
        
        min_length = float("inf")
        l = 3 * k
        r = len(s)

        while l <= r:
            mid = (l + r) // 2
            result = get_min_minutes(s, mid, k)
            if result:
                r = mid - 1
                min_length = min(min_length, mid)
            else:
                l = mid + 1

        return min_length if min_length != float("inf") else -1

def get_min_minutes(s, length, k):
    result = [0] * 3
    for c in s[:length]:
        result[ord(c) - ord("a")] += 1
    if check_enough(result, k):
        return True
    for right_num in range(1, length+1):
        result[ord(s[length-right_num]) - ord("a")] -= 1
        result[ord(s[-right_num]) - ord("a")] += 1
        if check_enough(result, k):
            return True
    return False

def check_enough(result, k):
    for r in result:
        if r < k:
            return False
    return True