문제 링크
문제
티어: 골드 3
알고리즘: 그리디
A, B, C로만 이루어졌고 길이가 |S|인 문자열 S가 있다. 당신은 이 문자열에 다음과 같은 시행을 할 수 있다.
- A와 그 뒤에 있는 B를 지운다.
- B와 그 뒤에 있는 C를 지운다.
각 문자는 최대 한 번만 지울 수 있다.
예를 들어 ABCBA를 보자. 각 문자에 왼쪽부터 1번, 2번, 3번. . . 과 같이 번호를 붙이면 다음과 같이 시행할 수 있다.
-
1번 A와 2번 B를 지운다. 이 경우 시행의 횟수는 1번이고, 남은 문자열은 CBA이다. 어떤 두
문자를 골라도 시행의 조건을 만족시킬 수 없으므로, 더 이상 시행을 할 수 없다. -
1번 A와 4번 B를 지우고, 이어 2번 B와 3번 C를 지운다. 이 경우 시행의 횟수는 2번이고 남은 문자열은 A이다. 문자열에 남은 문자가 하나이므로, 더 이상 시행을 할 수 없다.
이외에도 시행을 할 수 있는 여러 경우의 수가 있다.
시행을 할 수 있는 최대 횟수를 구해라.
입력
첫 번째 줄에 문자열 S가 주어진다.
출력
첫 번째 줄에 답을 출력한다.
제한
- 1 ≤ |S| ≤ 300 000
- S의 모든 문자는 A, B, C 중 하나이다.
풀이
시행 횟수를 최대로 하는게 목적이다.
연산을 보면 A는 B를 지우고 B는 C를 지운다.
다시 말해서 C는 B로 지울 수 있고, B는 A로 지울 수 있지만, A를 지울 수 있는 알파벳은 없다.
그래서 우선 순위를 봤을 때 먼저 B를 이용해서 C를 지우는게 최선의 선택이라 할 수 있다.
왜냐하면 A로 B를 우선적으로 지우면, B로 지울 수 있었던 C를 못지울 수 있는 상황이 발생하고,
B를 이용해서 C를 우선적으로 지우면, 가능한 C를 최대한 지우기 때문에 그런 상황은 발생하지 않기 때문이다. 또 B가 지워진다고 해서 A가 덜 지워질 순 있어도, 어차피 그 C를 지운만큼 횟수가 같거나 커지기 때문에 문제 없다.
여기서 지울 때도 가장 앞에있는 B와 가능한 가장 앞에있는 C를 지워야 한다.
왜냐하면 B가 그보다 뒤에 있는 C를 지우면 다른 B가 지울 가능성을 없애기 때문이다.
예를 들어 BCCBC라고 했을 때 첫 번째 B가 마지막 C를 지웠다고 해보자, 횟수는 1이 된다.
다 지우고 나면 이제 A와 B를 매칭해야 한다.
A가 B를 지울 때도 똑같이 가장 앞에있는 A와 가능한 가장 앞에있는 B를 지워야 한다.
이유는 같다.
나는 이를 구현하기 위해서 큐를 사용했다. 큐에 B의 인덱스를 차례대로 넣고, C가 나올때 마다 앞에서 부터 빼면 된다.
그리고 A와 매칭할 때는 앞에서부터 B의 인덱스를 peek()하면서, 만약 A보다 앞에 있다면 다른 뒤에 있는 A와도 당연히 매칭되지 않기 때문에 poll() 해주고, 뒤에 있는 B가 최초로 나오면 그 B가 가능한 가장 앞에 있는 B이기 때문에 매칭해 주면 된다.
시간 복잡도는 O(N)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String S = br.readLine();
int answer = 0;
Queue<Integer> queue = new LinkedList<>();
//먼저 B로 C를 최대한 지운다.
for(int i=0; i<S.length(); i++) {
if(S.charAt(i) == 'B') {
queue.add(i);
} else if(S.charAt(i) == 'C') {
if(queue.size() != 0) {
queue.poll();
answer += 1;
}
}
}
//나머지 B를 A로 지운다.
for(int i=0; i<S.length(); i++) {
if(queue.size() == 0) {
break;
}
if(S.charAt(i) == 'A') {
while(queue.size() != 0 && queue.peek() < i) {
queue.poll();
}
if(queue.size() != 0) {
queue.poll();
answer += 1;
}
}
}
System.out.println(answer);
}
}