[백준] 1969번 : DNA - 자바[Java]

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

1969번: DNA

풀이

입력으로 들어온 모든 DNA와 Hamming Distance의 합이 가장 작은 DNA 를 출력해야 한다. 뉴클레오티드는 총 4가지이므로, 입력으로 들어온 n개의 DNA의 각 자리에 있는 글자들을 비교하여, Hamming Distance의 합이 가장 작은 뉴클레오티드를 찾으면 된다.

 

로직

1. n과 m을 입력받는다.

2. 입력으로 들어오는 DNA 문자열을 저장할 String[] dna를 선언하고 크기는 n을 할당한다.

3. 뉴클레오티드를 char형 배열 acgt에 저장한다.

char[] acgt = {'A', 'C', 'G', 'T'};

4. 입력으로 들어오는 DNA 문자열을 dna 배열에 저장한다.

5. Hamming Distance의 합이 가장 작은 DNA를 저장할 StringBuilder형 변수 sb와 그 Hamming Distance의 합을 저장할 answer를 선언하고, answer은 0으로 초기화한다.

6. 각 자리의 글자마다 다음을 수행한다. (총 m번 반복)

• Hamming Distance의 합의 최솟값을 저장할 min과 글자를 저장할 ch를 선언한다.
• 현재 위치의 글자가 각 뉴클레오티드('A', 'C', 'G', 'T')일 때 Hamming Distance의 합을 구한다. 최솟값인 경우 그 값을 min에 저장하고 ch도 변경한다. 문제에서 "DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다."고 나와있으므로, Hamming Distance의 합이 이전에 구한 min값과 작을 때만 min과 ch를 변경한다.

        for (int i = 0; i < m; i++) {

            int min = Integer.MAX_VALUE;
            char ch = 'a';
            for (int j = 0; j < 4; j++) {
                int dis = hammingDistance(acgt[j], dna, i);

                if (dis < min) {
                    min = dis;
                    ch = acgt[j];
                }
            }

• min값을 answer에 더하고 ch를 sb에 더한다.

7. sb와 answer를 출력한다.

 

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        String[] dna = new String[n];
        char[] acgt = {'A', 'C', 'G', 'T'};
        
        for (int i = 0; i < n; i++) {
            dna[i] = br.readLine();
        }
        
        StringBuilder sb = new StringBuilder(); //Hamming Distance의 합이 가장 작은 DNA
        int answer = 0; //그 Hamming Distance의 합

        for (int i = 0; i < m; i++) {

            int min = Integer.MAX_VALUE; //현재 위치에서 Hamming Distance의 합의 최솟값
            char ch = 'a'; //현재 위치에서 Hamming Distance의 합의 최솟값이 되도록 하는 글자
            
            for (int j = 0; j < 4; j++) {
                int dis = hammingDistance(acgt[j], dna, i);

                if (dis < min) {
                    min = dis;
                    ch = acgt[j];
                }
            }

            answer += min;
            sb.append(ch);
        }

        System.out.println(sb);
        System.out.println(answer);
    }

    //idx번째 글자가 ch일 때, dna의 모든 DNA 문자열의 idx번째 글자와의 Hamming Distance의 합을 리턴
    public static int hammingDistance(char ch, String[] dna, int idx) {

        int cnt = 0;

        for (int i = 0; i < dna.length; i++) {
            if (ch != dna[i].charAt(idx))
                cnt++;
        }

        return cnt;
    }
}

 

---

다른 풀이 2

각 위치에 대해 반복문(m번)을 진행할 때, 현재 위치의 글자가 각 뉴클레오티드('A', 'C', 'G', 'T')일 때 모든 DNA와 검사해서 Hamming Distance의 합을 구하는 것이 아니라, int[] cnt = new int[4]를 선언한 다음 입력받은 DNA들의 뉴클레오티드 개수를 구해서 가장 최댓값인 뉴클레오티드를 찾아서 그 글자를 sb에 추가한다. answer에는 n - max를 더하면 된다.

for (int i = 0; i < m; i++) {

            int max = Integer.MIN_VALUE;
            int idx = 0;
            int[] cnt = new int[4];

            for (int j = 0; j < n; j++) {
                switch(dna[j].charAt(i)) {
                    case 'A' : cnt[0]++; break;
                    case 'C' : cnt[1]++; break;
                    case 'G' : cnt[2]++; break;
                    case 'T' : cnt[3]++; break;
                }
            }

            for (int j = 0; j < 4; j++) {
                if (max < cnt[j]) {
                    max = cnt[j];
                    idx = j;
                }
            }

전체 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        String[] dna = new String[n];
        char[] acgt = {'A', 'C', 'G', 'T'};

        for (int i = 0; i < n; i++) {
            dna[i] = br.readLine();
        }

        StringBuilder sb = new StringBuilder(); //Hamming Distance의 합이 가장 작은 DNA
        int answer = 0; //그 Hamming Distance의 합

        for (int i = 0; i < m; i++) {

            int max = Integer.MIN_VALUE;
            int idx = 0;
            int[] cnt = new int[4];

            for (int j = 0; j < n; j++) {
                switch(dna[j].charAt(i)) {
                    case 'A' : cnt[0]++; break;
                    case 'C' : cnt[1]++; break;
                    case 'G' : cnt[2]++; break;
                    case 'T' : cnt[3]++; break;
                }
            }

            for (int j = 0; j < 4; j++) {
                if (max < cnt[j]) {
                    max = cnt[j];
                    idx = j;
                }
            }

            answer += n - max;
            sb.append(acgt[idx]);
        }

        System.out.println(sb);
        System.out.println(answer);
    }

}

참고 : https://www.acmicpc.net/source/50226957

 

큰 차이는 없는 것을 확인할 수 있다.