[백준 온라인 저지] 1969. DNA

DNA란 어떤 유전물질을 구성하는 분자이다. 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자 A, T, C, G를 따서 표현한다. 그리고 Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클오티드 문자가 다른 것의 개수이다. 만약에 “AGCAT"와 ”GGAAT"는 첫 번째 글자와 세 번째 글자가 다르므로 Hamming Distance는 2이다.

우리가 할 일은 다음과 같다. N개의 길이 M인 DNA s1, s2, ..., sn가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 s1의 Hamming Distance + s와 s2의 Hamming Distance + ... + s와 sn의 Hamming Distance의 합이 최소가 된다는 의미이다.

 

1. 입력

- 첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다.

- 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

 

2. 출력

- 첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오.

- 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

 

3. 예제

 

4. 코드

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer token = new StringTokenizer(br.readLine());
        int n = Integer.valueOf(token.nextToken()), m = Integer.valueOf(token.nextToken());
        String[] dna = new String[n];
        for(int i=0 ; i<n ; i++)
            dna[i] = br.readLine();
        int[] count = new int[4]; // A, C, G, T의 개수를 저장
        int hd = 0;
        StringBuilder sb = new StringBuilder();
        for(int i=0 ; i<m ; i++){
            for(int j=0 ; j<n ; j++){
                char c = dna[j].charAt(i);
                if(c=='A') count[0]++;
                else if(c=='C') count[1]++;
                else if(c=='G') count[2]++;
                else count[3]++;
            }
            int max = 0;
            for(int j=1 ; j<4 ; j++)
                if(count[max]<count[j]) max = j;
            hd += n - count[max];
            if(max==0) sb.append('A');
            else if(max==1) sb.append('C');
            else if(max==2) sb.append('G');
            else sb.append('T');
            Arrays.fill(count, 0);
        }
        bw.write(sb.toString()+"\n"+hd);
        bw.flush(); bw.close();
    }
}

- 18732KB, 180ms