[BOJ] 1969 : DNA(Java)

문제

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자를 따서 표현한다. 만약에 Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-Cytosine-Cytosine-Guanine-Adenine-Thymine로 이루어진 DNA가 있다고 하면, “TAACTGCCGAT”로 표현할 수 있다. 그리고 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와 s3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

입력

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

출력

첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

---

💡풀이

주어진 DNA 문자열들을 String 배열에 저장한 뒤, 각 자리의 글자들을 비교해 가장 많이 사용된 문자(뉴클레오티드)를 연결해주면 된다. 각 자리의 문자들을 입력 받아 ArrayList를 이용하여 연결한 뒤, Collections.frequency() 메서드를 이용해 이 값이 최댓값이 나오는 문자를 반환하여 연결하였다.

전체 코드는 다음과 같다.

import java.util.*;

public class Main {
    public static String findValue(int index, String[] list){

        List<String> temp_list=new ArrayList<>();
        String check_str = "ACGT";
        for(int i=0;i< list.length;++i)
        {
            temp_list.add(Character.toString(list[i].charAt(index)));
        }

        int max=0;
        String result="";
        for(int i=0;i<check_str.length();++i){
            int count = Collections.frequency(temp_list, Character.toString(check_str.charAt(i)));
            if(count>max)
            {
                result = Character.toString(check_str.charAt(i));
                max = count;
            }
        }
        
        return result;
    }

    public static int getCount(String origin, String answer){
        int result=0;
        for(int i=0;i<origin.length();++i){
            if(origin.charAt(i)!=answer.charAt(i))
                result++;
        }
        return result;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        String[] list = new String[N];
        for(int i=0;i< list.length;++i){
            list[i]=sc.next();
        }

        String answer = "";
        for(int i=0;i<M;i++) {
            answer += findValue(i,list);
        }

        int count=0;
        for(int i=0;i<N;++i){
            count += getCount(list[i],answer);
        }

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