[백준] 자바 1969 DNA

문제

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가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

---

테스트 케이스

 

입력 1

6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

출력 1

AAGTTACCAA
12

 

입력 2

3 5
ATCGC
ACTGG
TACTT

출력 2

7

 

입력 3

3 3
TAC
GCA
AGT

출력 3

AAA
6

---

접근

그리디식으로 접근하여 매번 세로로 가장 많이나온 알파벳을 고르면 답이 됩니다.

 

TACG

그림처럼 세로로 가장 많이 나온순으로 정답이 됩니다.

첫 번째 칸 T 2개 , A 1개 => T

두 번째 칸 A 3개 => A

세 번째 칸 A 2개, T 1개 => A

 

개수를 셀 때는

첫 번째 칸 T가 아닌 것 1개

두 번째 칸에서 A가 아닌 것 0개

세 번째 칸에서 A가 아닌 것 1개

... 이런식으로 구하니 문제가 해결 되었습니다.

---

코드

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


public class Main {
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//값 받기
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		String s[] = new String[N];
		for(int i=0; i<N; i++) {
			s[i] = br.readLine();
		}
		
		int sum = 0;
		String result = "";
		//DNA 수 * DNA 줄길이
		for(int i=0; i<M; i++) {
			int max = -(int)1e9;
			int maxIndex = 0;
			int arr[] = new int[4];
			for(int j=0; j<N; j++) {
				if(s[j].charAt(i) == 'A') arr[0]++;
				else if(s[j].charAt(i) == 'C') arr[1]++;
				else if(s[j].charAt(i) == 'G') arr[2]++;
				else arr[3]++;
			}
			for(int j=0; j<4; j++) {
				if(arr[j] > max) {
					max = arr[j];
					maxIndex = j;
				}
			}
			if(maxIndex == 0) result+="A";
			else if(maxIndex == 1) result+="C";
			else if(maxIndex == 2) result+="G";
			else if(maxIndex == 3) result+='T';
			for(int j=0; j<4; j++) {
				if(j != maxIndex) {
					sum += arr[j];
				}
			}
		}
		bw.append(result+"\n");
		bw.write(String.valueOf(sum));
		bw.flush();
		br.close();
		bw.close();
	}

}

---

주의

개수가 같을 때는 사전순으로!