[LeetCode] 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.

 

💫 예시

Input: s = "aabaaaacaabc", k = 2
Output: 8
Explanation: Take three characters from the left of s. You now have two 'a' characters, and one 'b' character. Take five characters from the right of s. You now have four 'a' characters, two 'b' characters, and two 'c' characters. A total of 3 + 5 = 8 minutes is needed. It can be proven that 8 is the minimum number of minutes needed.

 

🎱 제한

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

 

📚 문제 풀이

꽤 재미있는 문제였다.

 

문제를 정리해보자면, a,b,c만 포함되어 있는 문자열이 주어지고, 각 a,b,c가 최소 k개 이상 포함하도록 prefix와 suffix를 구성할 때, 이 prefix와 suffix 길이를 최소로 만드는 문제였다. prefix와 suffix를 둘 다 합쳐서 k개 이상이면 된다. 

 

예를 들어 s=aabaaaacaabc이고 k=2 일 때 prefix= "aab", suffix="caabc"로 구성하여 총 8이 되는 것이 최소 값이다. 

 

문제 제목부터 left, right라 투포인터 냄시가 났는데, 어떻게 포인터를 움직여야 할지 감이 안잡혔다. 지금까지 봐왔던 투포인터랑은 살짝 느낌이 다른게 prefix도 구성해줘야 했고, suffix도 만들어 줘야 했다.

 

두 번 투포인터를 돌려야 하나? 라는 질문이 생겼고 그러면 기준점을 어떻게 잡아야 하는거지? prefix에서 얼마만큼 만족시키고 suffix 만들러 가야하는거지? 등등 오히려 더 혼란스러웠다. 

 

핵심은 뒤집기였다. 

 

무엇을 뒤집어야할까, 문자열을? 아니다. 내가 가지고 있던 고정관념을 뒤집어야 했다. 

 

투포인터로 prefix도 만들고, suffix도 만드는 것이 고민이었는데, prefix와 suffix를 투포인터로 만드는 것이 아니라 역으로 문자열에서 투포인터로 prefix와 suffix에서 제외할 부분을 찾는 것이다! 

 

처음에 구상했던 것

 

 

위 그림처럼 prefix와 suffix를 찾는 것이 아니라, 아래처럼 지울 부분을 찾기만 하면 자연스럽게 prefix와 suffix가 구해진다.

 

뒤집기

 

 

제일 처음 우선 문자열에서 a,b,c를 카운트 해주고 이때 최소값이 k보다 작다면 요구사항을 만족시킬 수 없으니 -1을 리턴한다. 

그리고 right 포인터를 1씩 증가시킬 예정인데, 이동시켰더니 a,b,c 최소값이 k보다 작아진다면 다시 k보다 같을때까지 left를 1씩 증가시킨다. 

 

아이디어가 굉장히 재미있었던 문제였다. 뭔가 갈피를 못잡고 있을 때, 뒤집어서 생각해보면 힌트를 얻을 수 있다는 것을 다시금 깨달았다. 

 

💻 코드

 

 

🔗 문제링크