백준 233328 (마을 구하기)

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

23328번: 마을 구하기

폭탄을 뭉쳐놓아야 우리가 원하는 문제를 해결 가능 

왜냐면 폭탄을 쉴드나 벽으로 감싸서 최대한 마을과 인접한 폭탄이 없도록 만들기 위함이다. 

 

문자열로 받고 폭탄을 방어할 쉴드가 몇개인지 세준다. 

 

 

2개 이상 

1개 

0개 

 

간단한 0개부터 

 

가장 좌측 or 가장 우측에 모아두면 0개에서 1개의 마을이 폭파된다. 0개인경우는 마을이 없는 경우

 

BBBB... -> 1

....BBBB -> 2

 

1번은 B보다 앞선 문자가 존재하지 않을때

 

2번은 B보다 앞선 문자가 존재할때  

 

 

1개일 때에는 

 

가장 좌측 or 가장 우측에 모아두고 쉴드로 방어하면 0개의 마을이 폭파된다. 

BBBb... -> 1 

...bBBB -> 2

 

1번은 B보다 앞선 문자가 존재하지 않을때

 

2번은 B보다 앞선 문자가 존재할때 

 

 

2개이상 때에는 

 

...bBBBb... -> 1

BBBb.... -> 2

...bBBB -> 3

 

 

1번은 앞과 뒤에 어떤 문자들이 존재하고, 앞에 문자들은 모두 b보다 작고, 뒤에 문자들은 모두 b보다 클때 

 

2번은 B보다 사전순 앞선 문자가 존재하지 않을 때

 

3번은 b보다 사전순 뒤에 문자가 존재하지 않을 때

근데 이 경우를 잘 생각해보면 

 

...bbBBB꼴이 되는데 이건 ...bBBBb꼴보다 사전순으로 더 뒤에 있게 됨 

 

여기에 쉴드랑 폭탄 제거시 empty되는 경우 case 처리 해주면 됨 

 

 

아직 이렇게 케이스 워크를 하는게 익숙치 않다. 생각을 쪼개서 정리좀해보자

뭘 찾으려는 건지 

 

내가 체크하는 케이스가 사전순으로 가장 앞서야 한다는 조건을 확인해야 하는데 이걸 계속해서 확인하지 못했다... 

 

이 문제 풀면서 erase와 insert 에 대해서 공부하고 s=s+a+b 등 이런 연산을 할 수 있다는 걸 많이 알게되었다.

#include <bits/stdc++.h>

using namespace std;
#define TEST int tt; cin >> tt; while (tt--)
#define all(v) (v).begin(), (v).end()
#define loop(e, v) for (auto& (e) : (v))
#define mem(v, e) memset((v), (e), sizeof(v))
#define _unique(v) (v).erase(unique((v).begin(),(v).end()),(v).end())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define xx first
#define yy second
#define ll long long
#define ld long double
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(0);
const int MAX = 1005;
const int INF = 1e9 + 1;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;

int main() {
    FASTIO
    string s;
    int N, cnt = 0, sh = 0;
    char bomb;
    cin >> N >> bomb;
    cin >> s;
    sort(all(s));
    int start = -1;
    char a = (char) ((int) bomb + 32);
    for (int i = 0; i < N; i++) {
        if (s[i] == bomb) {
            if (start == -1)start = i;
            cnt++;
        }
        if (s[i] == a)sh++;
    }
    s.erase(start, cnt);
    string b;
    while (cnt--)b.push_back(bomb);
    if (sh >= 2) {
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == a) {
                s.erase(i, 2);
                break;
            }
        }
        int index = lower_bound(all(s), a) - s.begin();
        if (s.empty()) {
            s += b + a + a;
        }
        else{
            if(s[0]>=bomb){
                s+=a;
                sort(all(s));
                s = b+a+s;
            }
            else if(s[s.length()-1]<=a){
                s+=a;
                sort(all(s));
                s=s+a+b;
            }
            else {
                string c = a + b + a;
                s.insert(index, c);
            }
        }
    } else if (sh == 1) {
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == a) {
                s.erase(i, 1);
                break;
            }
        }
        if(s.empty()){
            s=b+a;
        }
        else{
            if(s[0]>=bomb)s=b+a+s;
            else s=s+a+b;
        }
    } else {
        if (s[0] >= bomb)s = b + s;
        else s = s + b;
    }
    cout << s << '\n';
}