Codeforces Round #734 (Div. 3)-C. Interesting Story

문제 설명

커리는 소설을 쓰고 싶다. 커리는 진짜 이상한 작가인데 오직 문자 'a', 'b', 'c', 'd', 'e'만 사용한다.

이야기를 구성하기 위해서 커리는 주어진 소문자만으로 이루어진 단어 $n$개를 작성했다. 커리는 재밌는 이야기를 만들기 위해서 선택해야 하는 최대 단어수를 구해야 한다.

단어를 선택하는 순서는 중요하지 않다. 이야기를 구성하는 모든 단어에 있는 5개의 문자중 한 문자의 개수가 다른 4개의 모든 문자의 개수 총합보다 큰 경우가 있으면 이 이야기는 흥미로운 이야기라고 한다.

예를 들어 이야기가 3단어 "bac", "aaada", "e"로 이루어져 있다면 이 이야기는 흥미로운 이야기이다. 왜냐하면 단어 'a'가 5번 나타났고, 다른 모든 단어가 총 4번 나타났기 때문이다. 그러나 두 단어 "aba", "abcde"로 이루어진 이야기는 흥미로운 이야기가 아니다.

문자 'a', 'b', 'c', 'd', 'e'로만 이루어진 단어 $n$개의 수열이 주어진다. 우리는 흥미로운 이야기를 만들기 위한 단어의 최대 개수를 구해야 한다. 만약 이러한 이야기가 하나도 없으면 $0$ 을 출력한다.

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 5000)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 수열에 포함된 단어의 개수 $n (1 \le n \le 2 \cdot 10^5)$ 이 주어진다.

다음 $n$개의 줄에는 소문자 5개로 이루어진 공백이 아닌 문자열이 주어진다. 수열에 있는 단어는 중복이 가능하다. 이 단어는 오직 문자 'a', 'b', 'c', 'd', 'e'로만 이루어져 있다.

각 테스트 케이스의 두번째 줄에는 정수 $n$ 개 $a_1, a_2, ..., a_n (1 \le a_i \le n)$ 이 주어진다.

Output
각 테스트케이스마다 재미있는 이양기를 구성하기 위해서 필요한 단어의 최대 개수를 출력한다. 만약 그러한 경우가 없다면 $0$ 을 출력한다.

Example
input
6
3
bac
aaada
e
3
aba
abcde
aba
2
baba
baba
4
ab
ab
c
bc
5
cbdca
d
a
d
e
3
b
c
ca

output
3
2
0
2
3
2

문제 접근

사용한 알고리즘: 그리디 알고리즘, 문자열, 정렬
걸린 시간 : 00:16
그리디 알고리즘이라는 건 알았지만 어떻게 접근을 해야할지 모르겠었다. 그러고 editoral을 보고나서 한 식만 정의하면 나머지는 스무스하게 풀린다는 사실을 깨닫고 그냥 너무 하기 싫어졌다. 언제까지 코드포스 문제한테 쳐맞아야하는지 잘 모르겠다.

우리는 먼저 흥미로운 이야기의 정의를 알아야 한다. 흥미로운 이야기는 한 문자의 전체 개수가 다른 문자의 전체개수의 총합보다 많아야 한다는 조건이다.

그렇다면 우리는 이 함수를 한번 정의해 보자.
$f(s, k) = $ 단어 $s$에 있는 문자 $k$의 개수 - 단어 $s$에 있는 문자 $k$를 제외한 문자의 총 개수

이렇게 함수를 정의하면 수열의 원소를 $s_1, s_2, ... s_i$라고 하면 이 수열이 흥미로운 이야기가 되기 위해서 $f(s_1, k) + f(s_2, k) + f(s_3, k) + ... + f(s_i, k) > 0$ 이라는 식을 반드시 만족해야한다.
즉 k가 나올 수 있는 경우는 'a', 'b', 'c', 'd', 'e' 총 5가지이기 때문에 5번 반복해 $n$이 $200000$ 이므로 충분히 1초 안에 들어올 수 있다.

흥미로운 이야기의 단어 개수가 최대가 되려면 무조건 가장 큰 함수 값부터 차근차근 단어를 추가해야 하기 때문에 각 문자에 있는 단어의 $f(s, k)$ 값을 내림차순으로 정렬하고 함수값을 더한 결과가 0보다 작아지는 순간을 그 문자의 최대값이라고 하면 된다. 그리고 5개의 문자중 최대 값을 출력하면 이 문제는 풀리게 된다.

정답 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

char alpha[5] = {'a', 'b', 'c', 'd', 'e'};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        string arr[n];
        for(int i = 0; i < n; i++) cin >> arr[i];
        int ans = -1;
        for(auto al : alpha){
            vector<int> cnt;
            for(int j = 0; j < n; j++){
                int cur = 2 * count(arr[j].begin(), arr[j].end(), al) - arr[j].size();
                cnt.push_back(cur);
            }
            sort(cnt.begin(), cnt.end(), greater<int>());
            if(cnt[0] <= 0){
                ans = max(ans, 0);
                continue;
            }

            int sum = 0, k = 0;
            for(k = 0; k < cnt.size(); k++){
                sum += cnt[k];
                if(sum <= 0) break;
            }
            ans = max(ans, k);
        }
        cout << ans << "\n";
    }
    return 0;
}