[백준 25381] ABBC

문제 출처 : https://www.acmicpc.net/problem/25381

 

A와 B를 지우는 방법을 시행 1이라고 하고, B와 C를 지우는 방법을 시행 2라고 하면 결국 B가 이 문제의 핵심 입니다. 시행 1을 실행함으로 시행 2를 실행 못하는 경우가 생기고, 시행 2를 실행함으로 시행 1을 실행 못하는 경우가 생기기 때문 입니다.

DP로 생각할 수도 있지만 문자열의 길이가 30만 이나 되기 때문에 DP로는 해결할 수 없습니다. 좀 더 생각해보면 그리디로 문제를 해결할 수 있습니다.

문제 이해하기

결국 B의 개수가 문제 입니다. 시행 1과 시행 2 모두 B를 포함하기 때문에 A와 C가 아무리 많다고 하더라도 B의 개수 이상을 만들 수 없습니다. 따라서 시행 1이 가능한 개수와 시행 2가 가능한 개수를 모두 구한 다음 B의 개수를 확인하여 더 작은 쪽이 답이 됩니다.

코드 작성하기

코드를 작성해 보겠습니다.

초기화하기

S = list(input())
N = len(S)
ans = 0
cnt_a = 0
cnt_b = 0
cnt_all_b = 0

먼저 문자열 S를 입력 받습니다. 다음으로 문자열의 길이 N은 len 함수를 통해 구해 줍니다.

ans는 정답의 길이를 초기화 하였습니다. cnt_a는 시행 1의 개수를 구하기 위한 것입니다. cnt_b는 시행 2의 개수를 구하기 위한 것입니다. cnt_all_b는 b의 전체 개수를 구하기 위한 것입니다.

시행 1 구하기

for i in range(N):
    if S[i] == 'A':
        cnt_a += 1
    elif S[i] == 'B' and cnt_a:
        cnt_a -= 1        
        ans += 1

시행 1은 먼저 A가 존재하고, 다음으로 B가 있어야 합니다. 예를 들어 문자열 S가 BA의 경우에는 시행 1을 실행할 수 없습니다. 따라서 먼저 A가 존재하고 B가 존재할 때 ans를 더해줍니다. A가 존재할 때마다 cnt_a에 1을 더해주고, B가 존재하면 cnt_a에 1을 빼서 ABB의 경우는 체크가 되지 않도록 합니다. 최종적으로 ans에 시행 1이 가능한 개수가 저장 됩니다.

시행 2 구하기

for i in range(N):
    if S[i] == 'B':
        cnt_b += 1
        cnt_all_b += 1
    elif S[i] == 'C' and cnt_b:
        cnt_b -= 1
        ans += 1  

시행 2의 개수 역시 시행 1과 마찬가지로 구해줍니다. ans에는 기존 시행 1의 개수에 시행 2의 개수가 더해집니다. 그리고 cnt_all_b에는 B의 모든 개수가 저장됩니다.

결과 출력하기

print(min(ans, cnt_all_b))

최종 결과를 출력합니다. ans에는 시행 1과 시행 2의 전체 합계가 들어가 있습니다. cnt_all_b에는 문자열 S에 있는 전체 B의 개수가 들어가 있습니다. 두 값중 작은 값이 답이 됩니다.

전체 코드

전체 코드를 확인해 보겠습니다.

S = list(input())
N = len(S)
ans = 0
cnt_a = 0
cnt_b = 0
cnt_all_b = 0

for i in range(N):
    if S[i] == 'A':
        cnt_a += 1
    elif S[i] == 'B' and cnt_a:
        cnt_a -= 1        
        ans += 1

for i in range(N):
    if S[i] == 'B':
        cnt_b += 1
        cnt_all_b += 1
    elif S[i] == 'C' and cnt_b:
        cnt_b -= 1
        ans += 1

print(min(ans, cnt_all_b))