[백준] 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[] cntArr = new int[26];
        for (char c : str.toCharArray()) {
            cntArr[c - 'A']++;
        }

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

        System.out.println(min);
        System.out.println(getDNA(N, cntArr, min));
    }

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

2. 풀이 [C++]

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

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

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

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

    int cntArr[26] = {};
    for (char c : s) {
        cntArr[c - 'A']++;
    }

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

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

---

3. 풀이 정보

1. 풀이 [Java]

언어	시간	메모리	코드 길이
Java 11	112 ms	14188 KB	830 B

2. 풀이 [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2168 KB	597 B

---