백준 1969번
https://www.acmicpc.net/problem/1969
문제
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가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다
예제 입력
5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA예제 출력
TAAGATAC
7ACGTACGTAA
6생각하기
이번 문제는 쉽게 풀릴 것 같으면서도 복잡한 문제였다.
문자 하나를 여러개 붙여서 하나를 만든다 생각하면 되는데,
Hamming Distance의 합이 가장 작은 DNA를 출력하라는 문제였는데, Hamming Distance는 문자가 다를 때 증가하니까 결국에 가장 많이 나온 문자를 선택해서 문자열을 만들면 되는 문제이다.
동작
N = Integer.parseInt(st.nextToken()); // DNA의 수
M = Integer.parseInt(st.nextToken()); // 문자열의 길이
arr = new String[N];
for(int i=0; i<N; i++) {
arr[i] = br.readLine();
}먼저 들어오는 유전자들을 arr 배열에 저장을 해줬다. 어차피 문자열의 길이는 모두 같기 때문에 N으로 한번만 반복해주면 된다.
이제 DNA() 함수를 실행시켜보자
// 각 글자마다 가장 많이 나온 글자를 result에 연결시킨다.
for(int i=0; i<M; i++) {
HashMap<Character, Integer> map = new HashMap<>();
max = 0;
for(int j=0; j<N; j++) {
String str = arr[j];
map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0)+1);
}
이제 유전자 문자열을 넣은 arr 배열에서 M만큼 한글자 씩 분리해서
전체를 순환해서 어떤 글자가 몇번 씩 나왔는 지 값을 세아려준다.
이 값은 Map형식이 잘어울리니까 글자를 key값, 나온 횟수를 value로 해서
map에 저장해준다.
Iterator<Entry<Character, Integer>> it = map.entrySet().iterator();
while(it.hasNext()) {
Entry<Character, Integer> entrySet = (Entry<Character, Integer>)it.next();
int value = entrySet.getValue();
char key = entrySet.getKey();
// 가장 많이 나온 알파벳 선택.
if( max < value ) {
max = value;
ch = key;
}
// 값이 같을 경우 사전순으로 나열
else if(max == value) {
// 기존에 있던 ch와 key값을 사전순서로 비교해야함
char temp = key;
int num1 = Character.getNumericValue(ch);
int num2 = Character.getNumericValue(temp);
if(num1 > num2) {
ch = temp;
}
}
}이제 map이 다 완성됬고
Iterator를 사용해서 value와 key을 뽑아낸다
여기서 우리는 가장 많이 나온 글자를 찾아야 하기때문에 max 변수를 사용해서
계속 최대값을 갱신하며 한 글자씩 result에 연결해 나가면
마지막 결과를 얻을 수 있다.
코드
import java.io.*; import java.util.*; import java.util.Map.Entry; public class Main { static int sum = 0; static String result = ""; static int N, M; static String arr[]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); arr = new String[N]; for(int i=0; i<N; i++) { arr[i] = br.readLine(); } DNA(); System.out.println(result); System.out.println(sum); } // End of main static void DNA() { char ch = ' '; // 문자 int max; // 최대값 for(int i=0; i<M; i++) { HashMap<Character, Integer> map = new HashMap<>(); max = 0; for(int j=0; j<N; j++) { String str = arr[j]; map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0)+1); } Iterator<Entry<Character, Integer>> it = map.entrySet().iterator(); while(it.hasNext()) { Entry<Character, Integer> entrySet = (Entry<Character, Integer>)it.next(); int value = entrySet.getValue(); char key = entrySet.getKey(); if( max < value ) { max = value; ch = key; } else if(max == value) { char temp = key; int num1 = Character.getNumericValue(ch); int num2 = Character.getNumericValue(temp); if(num1 > num2) { ch = temp; } } } sum += N - max; result += ch; } } // End of solution } // End of class
