[BaekJoon] 7977번 - 크리스 마틴 [Java][C++]

문제 링크

---

1. 문제 풀이

문자열로 올 수 있는 문자가 $A$, $C$, $G$, $T$ 네 종류일 때, 주어진 문자열과 유사도가 최소인 문자열에 대해 유사도와 문자열을 출력해야 하는 문제다. 주어진 문자열의 길이를 $n$ 이라 하고 $A$, $C$, $G$, $T$ 네 종류의 문자의 개수를 $a$, $c$, $g$, $t$ 라고 할 때 $n = a + c + g + t$ 가 된다. 이때 가장 적게 등장한 문자의 개수를 $m$ 이라 하면 $m = \min(a, c, g, t)$ 가 된다.

주어진 문자열에 대한 최소 유사도를 갖는 문자열을 $S$ 라고 했을 때, 만약 $S$ 의 최소 유사도가 $m$ 보다 작다면 $S$ 의 길이는 $n$ 인데 각 문자가 $m$ 개 보다 적어야 한다. 즉 각 문자가 최대한 많은 $m - 1$ 개씩 있어도 $n > 4 \times (m - 1)$ 이므로 최소 유사도가 $m$ 보다 작으면서 길이가 $n$ 인 문자열은 만들 수 없다. 즉 최소 유사도는 $m$ 부터 가능하며 이는 주어진 문자열에서 가장 적게 등장한 문자로만 구성한 경우도 해당한다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String str = br.readLine();

        int[] cnt = new int[26];
        for (char c : str.toCharArray()) {
            cnt[c - 'A']++;
        }

        int min = Math.min(Math.min(cnt[0], cnt[2]), Math.min(cnt[6], cnt[19]));

        System.out.println(min);
        System.out.println(getDNA(n, cnt, min));
    }

    static String getDNA(int n, int[] cnt, int min) {
        if (cnt[0] == min) return "A".repeat(n);
        if (cnt[2] == min) return "C".repeat(n);
        if (cnt[6] == min) return "G".repeat(n);
        return "T".repeat(n);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int cnt[26];

string get_dna(int n, int mn) {
    if (cnt[0] == mn) return string(n, 'A');
    if (cnt[2] == mn) return string(n, 'C');
    if (cnt[6] == mn) return string(n, 'G');
    return string(n, 'T');
}

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

    int n;
    string s;
    cin >> n >> s;

    for (char c : s) {
        cnt[c - 'A']++;
    }

    int mn = min({cnt[0], cnt[2], cnt[6], cnt[19]});

    cout << mn << '\n';
    cout << get_dna(n, mn);
}

---