[BaekJoon] 25381 ABBC (Java)

1.  문제 링크

https://www.acmicpc.net/problem/25381

2.  문제

요약

• A, B, C로만 이루어졌고 길이가 |S|인 문자열 S가 있습니다.
• 이 문자열에 다음과 같은 시행을 할 수 있습니다.
  • A와 그 뒤에 있는 B를 지웁니다.
  • B와 그 뒤에 있는 C를 지웁니다.
• 각 문자는 최대 한 번만 지울 수 있습니다.
• 시행할 수 있는 최대 횟수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 문자열의 길이가 1보다 크거나 같고 300,000보다 작거나 같은 문자열 S가 주어집니다. S의 모든 문자는 A, B, C 중 하나입니다.
• 출력: 첫 번째 줄에 답을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
	public int getMaxCount(String s) {
		int max = 0;
		Deque<Integer> a_indexes = new ArrayDeque<Integer>();
		Deque<Integer> b_indexes = new ArrayDeque<Integer>();
		for(int i = 0; i < s.length(); i++) {
			if(s.charAt(i) == 'A') {
				a_indexes.addLast(i);
			} else if(s.charAt(i) == 'B') {
				b_indexes.addLast(i);
			} else if(s.charAt(i) == 'C') {
				if(b_indexes.size() > 0) {
					max++;
					b_indexes.pollFirst();
				}
			} else {
				System.exit(1);
			}
		}
		while(b_indexes.size() > 0 && a_indexes.size() > 0) {
			if(a_indexes.getFirst() < b_indexes.getFirst()) {
				max++;
				a_indexes.pollFirst();
				b_indexes.pollFirst();
			} else {
				b_indexes.pollFirst();
			}
		}
		return max;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String s = br.readLine();
		br.close();
		Main m = new Main();
		bw.write(m.getMaxCount(s) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 문자열 S에서 a의 index를 저장할 Deque a_indexes와 b의 index를 저장할 Deque b_indexes를 생성합니다.
• Deque는 Double-Ended Queue의 줄임말로 Queue의 양쪽으로 요소를 삽입 또는 삭제를 수행할 수 있는 자료구조입니다.
• 그렇기 때문에 Deque는 어느 쪽으로 입력하고 어느 쪽으로 출력하냐에 따라 Stack으로 사용될 수도, Queue로 사용될 수도 있습니다.
• 문자열 S의 각 문자들을 확인하면서 만약 A라면 a_indexes에 해당 index를 마지막 쪽에 넣고 만약 B라면 b_indexes에 해당 index를 마지막 쪽에 넣어줍니다.
• 또한 만약 해당 문자가 C라면 이전에 B가 이미 존재하는지 Deque b_indexes를 통해 확인하고 만약 존재한다면 해당 문자를 B와 함께 지웁니다. 즉, 시행할 수 있는 최대 횟수를 나타내는 변수 max의 값을 1 증가시키고 Deque b_indexes에서 앞쪽에 있는 요소 하나를 지우며 문자열 S에서 처음 나온 B를 C와 함께 지웁니다.
• 문자열 S의 각 문자를 모두 확인한 후에 아직 문자열 S에 A와 B가 남아있다면, 즉 a_indexes의 크기와 b_indexes의 크기가 모두 0보다 크다면 둘 중 하나의 크기가 0이 될 때까지 A와 B를 지워나갑니다.
• a_indexes와 b_indexes에서 앞에 있는 요소 하나씩을 가져온 다음, 만약 a_indexes에서 꺼낸 요소의 값이 b_indexes에서 꺼낸 요소의 값보다 작다면 A가 B보다 앞에 있다는 뜻이므로 해당 index의 A와 B를 지울 수 있기 때문에 max의 값을 1 증가시키고 a_indexes와 b_indexes에서 각각 꺼낸 값을 해당 Deque에서 삭제합니다.
• 만약 a_indexes에서 꺼낸 요소의 값이 b_indexes에서 꺼낸 요소의 값보다 크다면 해당 A는 B보다 뒤에 있다는 뜻이므로 현재 꺼낸 A와 B를 같이 지울 수 없기 때문에 a_indexes에서 꺼낸 해당 요소를 Deque에서 삭제합니다.
• 이렇게 지워나가다가 A 또는 B가 문자열 S에서 모두 사라졌을 때의 max값이 시행할 수 있는 최대 횟수가 됩니다.