[백준] 25381번 ABBC (C++)

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

 

 

이 문제는 ABC로 구성된 문자열이 주어졌을때

 

2가지의 행동을 적절히 사용하여 최대의 행동을 몇 번 할 수있는지 구하는 문제이다.

 

1. A와 그 뒤에있는 B를 지운다.

2. B와 그 뒤에 있는 C를 지운다.

 

글로만 보면 어떻게 최대로 지우는지 잘 모르겠지만

 

아래 테스트 케이스 2개를 보면 어떤거 부터 먼저 지우는지 대충 감이 잡힌다.

 

 

테스트 케이스 1번 ABCBA를 보면 

앞에서부터 AB 또는 BC를 지우면 최대 1번밖에 지울 수 없다.

 

하지만 BC를 먼저 지우고 AB를 지우면 최대 2번을 지울 수 있다.

 

따라서 B와 짝이되는 C를 먼저 지운후 이후에 A를 지우는 것이 최대한 많이 지울 수 있다고 생각하였다.

 

이를 구현하기 위해선 deque를 사용하여 B의 인덱스를 저장하였고

 

앞에서부터 B와 짝이되는 C를 찾아서 앞에서 빼주었고

 

이후에 뒤에서부터 B와 짝이되는 A를 찾아서 뒤에서 빼주며 개수를 늘려주었다.

 

데크를 사용하여 O(1)로 삽입 삭제연산을 할 수 있기 때문에

시간복잡도는 O(N)이며 N은 최대 30만이기 때문에 충분히 1초안에 통과할 수 있다.

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1};
string s;

void solve() {
    int cnt = 0;
    deque<int> dq;

    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'B') {
            dq.push_back(i);
        }
    }

    for(int i = 0; i < s.size(); i++) {        // C 제거
        if(s[i] == 'C') {
            if(dq.size() != 0 && dq.front() < i) {
                dq.pop_front();
                cnt++;
            }
        }
    }

    for(int i = s.size()-1; i >= 0; i--) {
        if(s[i] == 'A') {
            if(dq.size() != 0 && dq.back() > i) {
                dq.pop_back();
                cnt++;
            }
        }
    }

    cout << cnt;
}

void input() {
    cin >> s;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}