[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. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = s의 길이)

---

3. 코드

풀이 [Java][C++]

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 s = br.readLine();

        int[] cnt = new int[26];
        for (char c : s.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);
    }
}

#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);
}

---