[Codeforces][Round #734][Div.3] C : Interesting Story (C++)

https://codeforces.com/contest/1551/problem/C

Problem - C - Codeforces

 

 

[난이도] Div.3
[유형] Greedy

[풀이]
n개의 a~e로 이루어진 문자열중에 i개의 문자열을 골랐을 때,
i개의 문자열에 포함된 한 문자(a~e 중 하나)가 나머지 문자들보다 많으면
이것을 Interesting story라고 합니다.

문제에서는 Interesting story를 만들 수 있으면서 i를 최대로 할때의 i값을 출력해야 합니다.

n제한 20만이기때문에 O(n)으로 해결해야 합니다.
Greedy 방식으로 해결이 가능합니다.

예를들어 n이 3이고 아래와 같이 문자열이 주어졌을 때,
bac
aaada
e

일단 알파벳이 a~e 5개밖에 안되기때문에
a가 제일 많은 경우, b가 제일 많은 경우 ... e가 제일 많은 경우
총 5가지의 경우를 가정하여 5가지를 모두 해보는 방식으로 접근합니다.

5가지 경우에 대해 문자열을 가장 많이 선택할 수 있는 경우의 문자열 갯수를 구하고
이중 최댓값이 정답이 됩니다.

bac [ a:1 , 나머지 :2]
aaada [ a:4 , 나머지 :1]
eaeeeb [ a:1 , 나머지 :5]
여기서 a가 가장 많은 경우를 구하면,
3개를 모두 선택하게 되면, a 6개, 나머지 8개로 Interesting story를 만족하지 못합니다.

그러므로 Interesting story가 될때까지 문자열을 한개씩 빼줘야 합니다.
여기서 Interesting story를 만들기 가장 유리한 순서로 문자열을 빼줍니다.
당연하게도 a의 개수보다 나머지 문자의 수가 많을수록 우선적으로 빼주는것이 유리합니다.
그말은 즉, Diff : (a의 개수) - (나머지 문자의 수) 가 작은 수부터 빼주는것이 유리하다는 말이됩니다.

위의 Diff를 각 문자열에 계산해보면
bac -> -1
aaada -> 3
eaeeeb -> -4
이므로 eaeeeb , bac 순으로 빼주는 것이 유리합니다.
vector에 Diff 값들을 넣어주고 정렬하면 순서대로 빼주는 것이 가능합니다.

3개의 문자를 포함했을때는 Diff가 -2였지만 eaeeeb를 빼줌으로써 +2가 됩니다.
전체 Diff가 양수가 되면 Interesting story를 만족하는 것이므로
a가 가장 많은 경우에 선택할 수 있는 문자열의 최대 수는 bac,aaada를 선택한 2가 됩니다.

b,c,d,e에 대해서도 위와 같은 연산을 해주고 이중 최댓값을 선택하면 됩니다.

 

 

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
int tc,n;
string arr[200001];

int getCnt(char target){
    int total_diff=0;

    vector<int> diff; // diff
    for(int i=0;i<n;i++){
        int cnt=0;
        for(char c : arr[i]){
            if(c==target){
                cnt++;
            }
        }
        int other = (int)arr[i].size()-cnt;
        diff.push_back(cnt-other);
        total_diff+=(cnt-other);
    }
    sort(diff.begin(),diff.end());
    for(int i=0;i<diff.size();i++){
        if(total_diff>0) {
            return n-i;
        }
        total_diff -= diff[i];
    }
    return 0;
}

void solve(){
    int ret=0;
    for(int i=0;i<5;i++){
        ret=max(ret,getCnt('a'+i));
    }
    cout <<ret<<'\n';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> tc;
    while(tc--){
        cin >> n; 
        for(int i=0;i<n;i++) cin >> arr[i];
        solve();
    }
}

 

 

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round734-Div.3/C.cpp