Codeforces Round #734 (Div. 3)-B1. Wonderful Coloring - 1

문제 설명

메리는 알파벳 소문자로만 이루어진 문자열을 좋아한다. 메리는 이 문자열에 속해있는 문자 하나 하나를 빨간색 분필 혹은 초록색 분필로 색칠하려고 한다. 안그러면 색칠을 안해도 좋다. 우리는 다음 조건을 만족하는 방식으로 문자열을 색칠하면 최고로 좋은 색칠이라고 말한다.

1. 문자열의 각 문자는 빨간색, 초록색 색깔중 하나만 색칠하거나 색칠하지 않아야 한다.
2. 같은 색깔로 색칠한 모든 두 문자는 서로 다른 문자여야 한다.
3. 빨간색으로 색칠한 문자와 초록색으로 색칠한 문자의 개수는 같아야 한다.
4. 위에서 언급한 3개의 조건을 만족하면서 색칠한 문자의 개수가 최대가 되어야 한다.

예를 들어 문자열 $s = kzaaa$인 경우 최고로 좋은 색칠의 한가지 경우는 다음과 같다.

우리는 최고로 환상적인 색칠인 경우에서 빨간색, 혹은 초록색으로 색칠한 개수의 최대값인 $k$를 구해야한다.

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

각 테스트 케이스의 첫번째 줄에는 소문자로 이루어진 공백이 아닌 문자열 $s$가 주어진다. 각 문자열의 글자수는 $50$을 넘지 않는다.

Output
각 테스트케이스마다 최고로 환상적인 색칠을 한 문자열에서 빨간색으로 색칠한 문자의 최대 개수 $k$를 출력한다.

Example
input
5
kzaaa
codeforces
archive
y
xxxxxx

output
2
5
3
0
1

문제 접근

사용한 알고리즘: 문자열, 그리디 알고리즘
걸린 시간 : 00:05
이것도 조금만 생각하면 쉽게 풀 수 있는 문제이다.

일단 우리는 생각을 해야하는게, 같은 문자는 최대 2가지 색깔로 밖에 색칠을 할 수 없다는 점이다. 그렇기 때문에 한 문자가 2개보다 많이 나타나도 빨간색, 초록색으로 색칠을 해서 1가지 경우밖에 나오지 않는다. 그렇다면 남은 문자는 무슨색으로 색칠을 해야할까? 색칠을 하면 안된다. 이것은 조건 2번을 보면 알 수 있다.

그렇다면 1번밖에 안나타나는 문자는 어떻게 해야할까? 그 문자의 개수를 모두 센 다음에 2로 나눠버리면 빨간색과 초록색으로 번갈아 칠할 수 있는 최대값이 나온다.

즉 문자 빈도수가 2이상인 알파벳의 개수를 a라고 하고 문자 빈도수가 1인 알파벳의 개수를 b라고 하면 우리가 구하고 싶은 답은 $a + b / 2$이다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        string s; cin >> s;
        int alpha[26] = {};
        for(int i = 0; i < s.size(); i++) alpha[s[i] - 'a']++;
        int one = 0, two = 0;
        for(auto x : alpha){
            if(x >= 2) two++;
            else if(x == 1) one++;
        }
        cout << two + one / 2 << "\n";
    }
    return 0;
}