1. 문제 및 접근
1717. Maximum Score From Removing Substrings
String 값을 주고, ab를 지우면 x점수, ba를 지우면 y점수를 얻을 수 있다
최대 얻을 수 있는 점수를 반환
높은 점수대로 그리디를 쓰면 될 것 같은데
전체 탐색하니 시간초과
StringBulider에 담아서 담을 때 마다 판별 후 삭제하자
Constraints:
- 1 <= s.length <= 10^5
- 1 <= x, y <= 10^4
- s consists of lowercase English letters.
2. 첫 풀이 (시간초과)
public int maximumGain(String s, int x, int y) {
// x가 ㄷ ㅓ큰지 y가 더 큰지에 따라 다른데
// 더 큰걸 판별하고 같다면 둘 중 하나로 하자
//현재 x제거했을 때와 y를 제거했을때의 값을 저장해가면서 두 분기로
// "cdbcbbaaabab" 의 경우 ab를 빼게되면 cdbcbbaaab, cdbcbbaa
// 그냥 같을 경우엔 비교하자 그리디로 해서 둘다 빼봐서
// 현재 돌면서 x먼저 빼고, 다음 스트링에서 또 x빼고 뺄 ㄱㅔ없음 y빼는 형식
int xCount1 = 0;
int yCount1 = 0;
while (s.contains(first) || s.contains(second)) {
//cdbcbbaaabab
if (x >= y) {
while (s.contains(first)) {
s = s.replaceFirst(first, "");
xCount1++;
}
while (s.contains(second)) {
s = s.replaceFirst(second, "");
yCount1++;
}
} else if (x <= y) {
while (s.contains(second)) {
s = s.replaceFirst(second, "");
yCount1++;
}
while (s.contains(first)) {
s = s.replaceFirst(first, "");
xCount1++;
;}
}
}
return (xCount1 * x) + (yCount1 * y);
}
전체 코드
우리가 원하는 건 최대한 많은 점수를 가지고 싶다.
그러려면 더 점수가 높은 String를 먼저 다 빼주고, 남은 S에서 작은 점수인 String을 빼줄 것
2-1. "ab"와 "ba" 정의
점수에 따른 ab와 ba는 변하지 않기에 미리 선언
ab와 ba는 static 변수로 저장 final도 쓸 걸 그랬나..
2-2. x의 점수가 더 크다면 ?
x가 크기에
while문을 x인 "ab"를 먼저 while문을 돌며, "ab"가 있는지, s.contains("ab")로 확인
s 는 s.에 "ab"를 지우기 위해 replaceFirst로 처음 만나는 값을 다 ab -> "";
그 후 몇 번 지웠는지 세어주기
다돌면 점수가 더 적은 ba를 지워줄 차례다.
같은 방식으로 지우고,
몇 번 지웠는지 세어주기
2-3. y가 크거나 같다면 ?
정확하게 같은 방식을 반대로 해주면 된다.
높은 점수에 해당하는 String을 먼저 지워주고, 다음 걸 지워주는 방식
(같으면 아무거나 해도 된다)
2-4. 시간 초과
생각해보면,
s.contains("ab")로 한 번 찾고,
또 s.replaceFirst로 찾고 지우고의 반복이라
0(n^2)의 시간 복잡도를 가깝게 가진다.
10^5의 수가 들어올 수 있으니.. 100억은 너무 많아보인다.
다른 방법을 찾아보자
3. O(n^2) Stack처럼 만들기
public int maximumGain(String s, int x, int y) {
if (x > y) {
return useStack(s, x, y, "ab","ba");
} else
return useStack(s, y, x,"ba","ab");
}
private int useStack(String s, int x, int y,String first, String second) {
int answerCount = 0;
StringBuilder sb = new StringBuilder();
int sLength = s.length();
for (int i = 0; i < sLength; i++) {
sb.append(s.charAt(i));
int length = sb.length();
if (length >= 2 && sb.substring(length - 2).equals(first)) {
sb.delete(length - 2, length);
answerCount = answerCount + x;
}
}
s = sb.toString(); // 빼고 남아진 s를 만들어주기
sb = new StringBuilder();
sLength = s.length();
for (int i = 0; i < sLength; i++) {
sb.append(s.charAt(i));
int length = sb.length();
if (sb.length() >= 2 && sb.substring(length - 2).equals(second)) {
sb.delete(length - 2, length);
answerCount = answerCount + y;
}
}
return answerCount;
}
방식은 StringBuilder에서 하나씩 문자를 넣어가다, "ab"와 "ba"를 만날 때 마다 삭제 시켜준다.
삭제된 횟수마다 점수를 더해가며 answerCount 만들어주기
이렇게 작동한다면 O(n)으로 줄일 수 있을 것이다.
3-1 .useStack함수 호출
기본은 비슷하게 x가 클 경우 x값과 y값을 그대로 전하고,
y가 크거나 같을 경우에는 반대로 수를 전달
3-2. useStack()
정답을 담을 answerCount와
s를 새로 만들어줄 정답 StringBuilder를 만들어주기
3-3. sb에 담으면서 "ab" 나 "ba" 빼주기
S를 탐색하면서
sb에 하나씩 넣어준다.
넣어줄 때 마다 현재 들어온 수가 "ab"나 "ba"인지 판별
(x와 y의 수에 따라 그에 해당하는 String만 먼저 다 제거한다.)
조건 식 2개를 만족해야 "ab"나 "ba"임을 알 수 있다.
- 만들어진 sb의 길이가 2와 같거나 넘어야 하고,
- sb.subString을 사용해, 현재 sb에서 length에 -2를 해주면 현재 2개의 String이 x나 y의 값이랑 같아야 한다.
ex) sb = "cvbab"
s.subString(5-2 = 3) = "ab"
끝에 들어온 두개의 char가 "ab"라면 현재 sb에서 제거해주기
sb.delete(5-2 = 3, 5) = "ab"
sb = "cvb"
그리고 그에 해당하는 점수를 answerCount에 누적해주면 된다.
y가 클 경우 반대로 값을 넣어서 순서만 바꿔주면 된다.
4. 마무리
좀 오래 걸리긴 한 것 같은데..
O(n^2) -> O(n)으로 만족 해야겠다.
여러 함수들을 안쓰다보면, 까먹을 때가 있어서 가끔 써줘야된다.
예를 들어 subString의 Start index나 End index가 가끔 헷갈려 한 번 생각하고 적용하게 된다.
요새 정처기, sqld, 리눅스 마스터 등
자격증을 따려고 노력중이라 알고리즘을 소홀히 하고 있는데, 지금 좀 더 고생해놓자.. 언젠간 되돌아 올테니