[Gold IV] ABBC - 25381

문제 링크

성능 요약

메모리: 27716 KB, 시간: 328 ms

분류

자료 구조, 그리디 알고리즘, 큐

문제 설명

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가 주어진다.

출력

첫 번째 줄에 답을 출력한다.

풀이

A 보다 큰 인덱스로 나오는 B를 지울 수 있고, B 보다 큰 인덱스로 나오는 C를 지울 수 있다. B는 A를 지우는데도 필요하고 C를 지우는데도 필요하다.즉 단어를 아무리 많이 지워봤자 B의 개수보다 많이 지울 수는 없다. C의 인덱스는 B의 인덱스보다 커야하니, 입력 받은 문자열을 순회하며, A,B,C 각각 큐에다가 인덱스를 삽입한 후에, 먼저 C를 지우고, 가능한 C를 다 지우고 난 뒤, B가 남았으면, 가능한 A를 지워가는 방식으로 문제를 해결할 수 있다.

import java.io.*;
import java.util.*;

class Main {

    public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));

    String S;
    Queue<Integer> As;
    Queue<Integer> Bs;
    Queue<Integer> Cs;
    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.init();
        main.solution();
    }

    void init() throws Exception {
        S = BR.readLine();
        As = new ArrayDeque<>();
        Bs = new ArrayDeque<>();
        Cs = new ArrayDeque<>();

        for (int i = 0; i < S.length(); i++) {
            if (S.charAt(i) == 'A') {
                As.add(i);
            } else if (S.charAt(i) == 'B') {
                Bs.add(i);
            } else {
                Cs.add(i);
            }
        }
    }

    void solution() {
        long answer = 0;
        while (!Bs.isEmpty()) {
            if (!Cs.isEmpty()) {
                if (Cs.peek() > Bs.peek()) {
                    Cs.remove();
                    Bs.remove();
                    answer += 1;
                } else if (!As.isEmpty()) {
                    if (Bs.peek() > As.peek()) {
                        Bs.remove();
                        As.remove();
                        answer += 1;
                    } else {
                        Bs.remove();
                    }
                }
            } else if (!As.isEmpty()) {
                if (Bs.peek() > As.peek()) {
                    Bs.remove();
                    As.remove();
                    answer += 1;
                } else {
                    Bs.remove();
                }
            } else {
                break;
            }

        }
        System.out.println(answer);
    }


}