[Leetcode 2516번 문제] 2516. Take K of Each Character From Left and Right

문제 상황

You are given a string s consisting of the characters 'a', 'b', and 'c' and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s.

Return the minimum number of minutes needed for you to take at least k of each character, or return -1 if it is not possible to take k of each character.

characters a, b, c로 이루어져있고, 음이아닌 정수 k가 있다. 매분, 제일 왼쪽이나 오른쪽 요소를 가져갈 수 있다.

각각의 a,b,c를 k개 씩 뽑는데 드는 최소의 시간을 말하라.

입력

• 1 <= s.length <= 10 ^ 5
• s consists of only the letters 'a', 'b', and 'c'.
• 0 <= k <= s.length

출력

int 로 돌면서 왼쪽 a를 찾는데 드는 비용 오른쪽을 찾는데 드는 비용을 리턴한다.

과정

1. 왼쪽부터 오른쪽까지 누적합을 한것과 오른쪽에서 왼쪽까지 누적합을 한 것을 구한다.
2. 왼쪽을 기준으로 k개중 남은애들만큼을 오른쪽 누적합에서 이진탐색으로 구한다
3. 그 둘의 인덱스 합중 작은것을 답으로 정한다.

알고리즘

class Solution {
public:
    int takeCharacters(string s, int k) {
        if (!k)
        {
            return 0;
        }
        vector<vector<int>> SS(3, vector<int>(s.length() + 1, 0));
        int answer = s.length() + 1;
        for (int i = 1; i <= s.length(); i++)
        {
            for(int j = 0; j < 3; j++)
            {
                int prev = i == 0 ? 0 : SS[j][i - 1];
                if (s[i - 1] - 'a' == j)
                {
                    SS[j][i] = prev + 1;
                }
                else
                {
                    SS[j][i] = prev;
                }
            }
        }
        vector<vector<int>> BB(3, vector<int>(s.length() + 1,0));
        for (int i = s.length(); i > 0; i--)
        {
            for(int j = 0; j < 3; j++)
            {
                int prev = i == s.length() - 1 ? 0 : BB[j][s.length() - i];
                if (s[i - 1] - 'a' == j)
                {
                    BB[j][s.length() - i + 1] = prev + 1;
                }
                else
                {
                    BB[j][s.length() - i + 1] = prev;
                }
            }
        }
        for (int i = 0; i <= s.length(); i++)
        {
            int maX = 0;
            for (int j = 0; j < 3; j++)
            {
                int remain = k - SS[j][i] - 1;
                // cout << remain << '\\n';
                int idx = upper_bound(BB[j].begin(), BB[j].end(), remain) - BB[j].begin();
                maX = max(maX, idx);
            }
            cout << maX << ' ' <<  i << '\\n';
            answer = min(answer, maX + i);
        }

        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j <= s.length(); j++)
            {
                cout << SS[i][j] << ':' << BB[i][j] << '\\t';
            }
            cout << '\\n';
        }
        cout << 'A';
        return answer == s.length() + 1 ? - 1: answer;
    }
};