백준(BOJ) 25381 - ABBC

핵심 자료구조 : Queue

 

※ B와 C를 먼저 결합시켜 지워야 최대 횟수를 구할 수 있다.

문제에 나와있는 예시 2번을 보면

ABCBBACBABB가 예시로 나와있다.

만약 차례대로 생각해서 지워본다면

(AB)C(B)B(A)(C)(B)(AB)B

1 1      2     3   2   3   44

4개의 묶음밖에 만들지 못한다.

 

하지만 A가 B를 잘 선택해 결합해본다면

(A)(BC)(B)(B)(A)(C)(B)(AB)B

1    22   1   3   4   3   4   55

와 같이 5개의 묶음을 만들 수 있다.

 

이런 일이 발생하는 이유는, A가 선택하는 B의 가치 때문이다.

여기서 말하는 가치의 높고 낮음은, B가 C와 결합 될 가능성에 달려있다.

예시를 보자.

ABCB

1 2 3 4

각 문자에 인덱스를 달아둔 예시이다. 여기서 1번 B와, 2번 4번에 존재하는 B의 가치는 다르다.

B라는 문자의 뒤에 C가 있다면, 해당 B는 A와의 결합 가능성과 더불어 C와도 결합 될 수 있기 때문이다.

결론적으로 최대 횟수를 뽑아내기 위해서는 A와 결합될 B는 4번에 위치한 B이어야 한다.

 

따라서 이 문제는, B를 가장 효율적으로 사용해 최대 횟수를 이끌어내는 것이 목표라고 할 수 있다.

위에서 서술하였듯 A가 C와 결합 될 가능성이 존재하는 B를 선택하게 된다면, 횟수에서 손해를 보게 된다.

 

그래서 쉽게 풀이하기 위해 B와 C를 먼저 결합시킨 후, 남은 B를 A와 결합시키게되면 최대 횟수에 도달하게 된다.

B와 C를 결합시킬 때에도, C가 선택할 B는 가장 먼저 나온 B이어야 한다. 나중에 나온 B는 앞에 A가 있을 확률이 더 높다.

 

1. B-C 결합

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
char[] line = br.readLine().toCharArray();
int answer = 0;
Queue<Integer> bIdx = new ArrayDeque<>();
boolean[] visited = new boolean[line.length];
// O(n)
for (int i = 0; i < line.length; i++) {
    char elem = line[i];
    if (elem == 'B') bIdx.offer(i);
    else if (elem == 'C'){ // C
        if (!bIdx.isEmpty()) {
            answer++;
            visited[bIdx.poll()] = true;
        }
    }
}

먼저 입력을 받아 char 배열로 바꾼 후, B를 만난다면 Queue에 넣어주고 -> C를 만난다면 먼저 나온 B를 찾아 답을 더한다.

C와 결합시킨 B를 체크하기 위해서 boolean 배열 하나를 사용했다.

 

2. A-B 결합, 출력

// O(n)
int Acnt = 0;
for (int i = 0; i < line.length; i++) {
    char elem = line[i];
    if (elem == 'B' && !visited[i]) {
        if (Acnt > 0) {
            Acnt--;
            answer++;
        }
    } else if (elem == 'A') Acnt++;
}
System.out.println(answer);

위에서 결합에 사용되지않은 B를 만난다면, 앞에 있던 A와 결합시켜 준다.

해당 코드를 보면 B를 만나는 순간 A를 하나 지워주므로, B와 A의 순서 관계에 대해서는 상관하지 않아도 된다.