1653. Minimum Deletions to Make String Balanced
문제
Input:
s = "aababbab"
Output:
2
요약:
'a'와 'b' 로만 이루어져 있는 문자열 s를 받아 최소한의 문자를 삭제하여 균형을 맞춰라
여기서 균형은 'a'가 앞에 먼저 오고 그 뒤에 'b'가 따라오는 형태를 말한다
즉 여기서 주어진 s = "aababbab"는 문자 두 개를 삭제하여 균형을 맞출 수 있는 가능성이 두 가지가 있다
- "aababbab" -> "aaabbb"
- "aababbab" -> "aabbbb"
s = "bbaaaaabb"의 경우에는 앞의 'b' 두 개를 없애는 것 외에는 다른 방법이 없다
조건:
1 <= s.length <= 10^5
s [i]는 오직 'a' 혹은 'b'만 들어올 수 있다
풀이 과정
설명:
vector <pair <char, int>> compressed를 선언해 주고 s를 순회하면서 pair <문자, 연속된 수>를 담은 배열은 완성시킨다
compressed는 압축된 s가 되고 여기서 인덱스를 기준으로 좌측은 'b'가, 우측은 'a'가 없어졌을 때의 삭제 횟수수를 구하고 그중 가장 최소한의 삭제 횟수를 반환한다
조금은 복잡하게 보일 수 있는데 s를 연속된 문자의 개수로 압축시키고 그를 기준으로 인덱스를 한 번만 순회하며 좌측에 있는 pair <'b', 연속된 수>, 우측은 pair <'a', 연속된 수>의 연속된 수(이는 곧 삭제 횟수와 같다)들을 모아가며 모든 순회 중에서 가장 최소한의 삭제 횟수를 반환하는 것이다
시간복잡도:
s 순회 한번 $n$
compressed를 한번 순회하며 양쪽으로 검색 $c^{2}$
$$O\left( n+c^{2}\right) $$
코드:
class Solution {
public:
int minimumDeletions(string s) {
int minDel = INT_MAX;
vector<pair<char, int>> compressed;
// compress s
int sLen = s.length();
char curChar = s[0];
int len = 0;
for (int i = 0; i <= sLen; ++i) {
if (curChar != s[i]) {
compressed.push_back({curChar, len});
curChar = s[i];
len = 1;
}
else
len++;
}
// find minmum delection
for (int i = 0; i <= compressed.size(); ++i) {
int delSize = 0;
for (int j = i - 1; j >= 0; --j) {
if (compressed[j].first == 'b')
delSize += compressed[j].second;
}
for (int j = i + 1; j < compressed.size(); ++j) {
if (compressed[j].first == 'a')
delSize += compressed[j].second;
}
minDel = min(minDel, delSize);
}
return minDel;
}
};
오답노트:
틀렸다...!!
시간 초과로 틀리게 되었다 그래서 이부분을 어떻게 줄일까 고민해 보았다
좌우로 'a'와 'b'의 개수가 몇 개가 있는지 미리 기억해 놓으면 인덱스를 따라 매번 찾아서 값을 모을 필요가 없지 않을까?
처음에 'a'와 'b'의 총개수를 구하고 이는 반복문을 돌기 전 오른쪽에 있는 'a'와 'b'의 개수가 된다
이를 가지고 compressed의 인덱스를 순회하며 좌, 우의 개수를 쉽게 구할 수 있을 것이다.
심지어 우리는 'a'의 개수만 가지고 있으면 된다!
우리가 필요한 것은 좌측의 'a', 우측의 'b' 개수이므로 처음 s를 순회할 때만 'a'의 개수를 구하고 'b'의 개수는 나중에 compressed를 순회하며 얻어가면 된다!
시간복잡도:
s 순회 한번 $n$
compressed 순회 한번 $c$
$$O\left( n+c\right) $$
코드:
class Solution {
public:
int minimumDeletions(string s) {
int sLen = s.length();
int minDel = INT_MAX;
int a = 0, b = 0;
vector<pair<char, int>> compressed;
// compress s
char curChar = s[0];
int len = 0;
for (int i = 0; i <= sLen; ++i) {
if (s[i] == 'a')
a++;
if (curChar != s[i]) {
compressed.push_back({curChar, len});
curChar = s[i];
len = 1;
}
else
len++;
}
// exception for there is no need loop
if (!a || a == sLen)
return 0;
// find minmum delection
for (int i = 0; i < compressed.size(); ++i) {
minDel = min(minDel, a + b);
if (compressed[i].first == 'b')
b += compressed[i].second;
else
a -= compressed[i].second;
}
minDel = min(minDel, a + b);
return minDel;
}
};P.S.
class Solution {
public:
int minimumDeletions(string s) {
int n = s.size();
int ans = 0;
int count_b = 0;
for(int i=0;i<n;i++){
if(s[i]=='b')count_b++;
else{
ans = min(ans+1,count_b);
}
}
return ans;
}
};와.. 사고방식이 아예 다르다
나의 경우에는 좌우로 찾아나갈 생각을 했는데 한 번의 순회로 찾는다니...
뇌에서 좌우로 지운다는 생각을 버려보자
대신 좌, 우의 'a', 'b'를 지우지 말고 그 사이에 있는 균형이 잘 잡혀있지 않은 문자열의 균형을 맞춰야 한다고 생각해 보자
"aaabbbbaabababb"
를 생각해 보자
우리는 여기서 양 끝에 제대로 놓여있는 "aaa", "bb"를 고려하지 않고 가운데의
"bbbbaababa"
만 고려하면 된다
여기서 'b'를 전부 지워야 할지 혹은 'a' 만을 전부 지워야할지 선택하면 되는 것이다.
내 이론을 증명함과 동시에 위의 코드를 이해하기 쉽게 바꿔보았다
class Solution {
public:
int minimumDeletions(string s) {
int n = s.size();
int start = 0, end = n - 1;
int ans = 0;
int count_a = 0;
int count_b = 0;
while (s[start] && s[start] == 'a') start++;
while (end >= 0 && s[end] == 'b') end--;
for (int i = start; i <= end; ++i) {
if (s[i] == 'a')
count_a++;
else
count_b++;
}
return (min(count_a, count_b));
}
};틀렸다!
이유는 간단했다 'b'만 지우다가 어느 구간부터는 'a'를 지우는 것이 더 효율적이었던 것
그렇다면 우리는 지우면서 'a'를 만나는 순간이 'a'를 지우는 것이 더 효율적인지를 알아야 하기에 최소 두 개의 변수만 있으면 된다
- 여태까지의 'b' 개수
- 'a'를 만나면 그 시점부터 'a'를 지우는 것이 맞는지, 그리고 동시에 그 전까지의 b의 개수를 포함한 값
이들은 곧, 처음 코드에서의 count_b와 ans가 되겠다
원효대사가 이런느낌이었을까..?
이 코드는 보기좋게 바꿀 필요 없이 그저 그 자체로 보기 쉬운 코드였으며 이 코드를 작성한 사람이 코딩능력이 뛰어나서가 아닌 문제의 본질을 제대로 파악했기에 나온 코드로 문제를 제대로 이해했다면 쉽게 받아들일 수 있는 코드였다.
언어를 다루는 능력도 중요하지만 내가 해결하고자 하는 알고리즘의 본질을 파악하고 원하는 방향으로 풀어낼 수 있는 능력이 가장 중요하다고 생각이 든다
그렇기에 수학적 사고가 어느정도 필요하다는 생각이 절실하게 드는 하루였다