(알고리즘) 백준 25381 java 자바

원종식·2022년 7월 27일

문제

백준 2531 ABBC : https://www.acmicpc.net/problem/25381

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 중 하나이다.

서브태스크

예제 입력 1

ABCBA

예제 출력 1

예제 입력 2

ABCBBACBABB

예제 출력 2

풀이

해당 문제는 조금 고민해보니 결과가 나왔다. 그리디와 큐를 활용해서 풀었다.
앞에서 부터 읽어가며 A가 나오면 A 큐에 index를 넣어주고 B가 나오면 B큐에에 index를 넣어주었다.
C를 만나면 이전에 나온 B가 있는경우(B 큐의 길이가 0이 아닌 경우) B큐에서 pop을 해주고 ans 카운트를 1 증가한다. 이렇게 쭉 읽게 되면 C가 빠질 수 있는 경우는 다 빠지고 남은 A큐와 B큐가 남게 된다.
이제 A를 차례로 빼주려고 한다.
A큐의 퍼스트 값이 B큐의 퍼스트보다 앞에 있는 경우 둘다 pop해주며 ans카운트를 증가시킨다. 만일 B큐의 퍼스트가 A큐의 퍼스트보다 앞에 있는 경우 B큐만 pop을 한다. 이러다 A큐 혹은 B큐의 길이가 0이되면 종료하고 ans를 출력한다.

코드

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


public class Boj25381 {
    public static void main(String args[]) throws IOException {
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        String get=bf.readLine();
        Deque<Integer> bCount=new ArrayDeque<Integer>();
        Deque<Integer> aCount=new ArrayDeque<Integer>();
        int ans=0;
        for(int i=0;i<get.length();i++){
            if(get.charAt(i)=='C'){
                if(bCount.size()>0&&bCount.getFirst()<i){//C보다 앞에 나온 b가 있을 경우
                    ans++;//C를 제거하며 ans카운트 증가
                    bCount.pollFirst();//가장 먼저 나온 B제거, (그리디)
                }
            }
            if(get.charAt(i)=='B'){
                bCount.addLast(i);//B큐에 인덱스 추가

            }
            if(get.charAt(i)=='A'){//A큐에 인덱스 추가
                aCount.addLast(i);
            }
        }
        //이렇게 되면 C를 빼고 남은 B인덱스만 B큐에 남게 된다.
        while(aCount.size()>0 && bCount.size()>0){
            if(aCount.getFirst()<bCount.getFirst()){
                ans++;
                bCount.pollFirst();
                aCount.pollFirst();
            }
            else{
                bCount.pollFirst();
            }
        }
        System.out.println(ans);
    }
}