7977번: 크리스 마틴

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


$O(n)$

제일 빈도가 작은 문자를 n번 출력하면 된다.
그러한 문자가 문자열 안에 c개 존재한다 해보자.
마틴의 문자열 안의 각 문자는 c개 보다 작아야 한다.
그럼, (마틴의 문자열 길이)<4*c<=n 모순.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, s[4], idx;
char c;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf(" %c", &c);
        if (c == 'A') s[0]++;
        if (c == 'C') s[1]++;
        if (c == 'G') s[2]++;
        if (c == 'T') s[3]++;
    }
    idx = min_element(s, s + 4) - s;
    printf("%d\n", s[idx]);
    for (int i = 0; i < n; i++) putchar("ACGT"[idx]);
    return 0;
}