문제
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 중에 다른 DNA들이랑 가장 많이 겹치는 DNA를 찾는 문제인 줄 알았는데 알고보니까 보기로 주어진 DNA들과 가장 많이 겹치는 DNA를 만드는 문제였다.
우선 한 DNA에 대해서 문자열을 다 비교하고 다음 DNA에 대해서 비교하는 방법으로 진행하면 효율성이 너무 떨어지므로 세로줄로 봐서 DNA의 한 열에서 가장 많이 쓰이는 뉴클레오티드를 찾아서 문자열을 만드는 방식으로 풀면 된다.
package bruteForceSearch;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.StringTokenizer;
public class boj_1969 {
static int N, M;
static String[] DNA;
static StringBuilder nowDNA = new StringBuilder();
static int sum;
static void input() {
FastReader scan = new FastReader();
N = scan.nextInt();
M = scan.nextInt();
DNA = new String[N];
for (int i = 0; i < N; i++) {
DNA[i] = scan.next();
}
}
static void findMostNucleo(int index) {
HashMap<Character, Integer> nucleo = new LinkedHashMap<>(4);
nucleo.put('A', 0);
nucleo.put('C', 0);
nucleo.put('G', 0);
nucleo.put('T', 0);
for (int i = 0; i < N; i++) {
char now = DNA[i].charAt(index);
nucleo.put(now, nucleo.get(now) + 1);
}
char mostNucleo = 'A';
int max = 0;
for (Character key : nucleo.keySet()) {
if (max < nucleo.get(key)) {
sum += max;
max = nucleo.get(key);
mostNucleo = key;
} else {
sum += nucleo.get(key);
}
}
nowDNA.append(mostNucleo);
}
public static void main(String[] args) {
input();
for (int i = 0; i < M; i++) {
findMostNucleo(i);
}
System.out.println(nowDNA);
System.out.println(sum);
}
}
'Alcoholithm > 오답노트' 카테고리의 다른 글
[BOJ] 1010 다리 놓기 (0) | 2023.09.18 |
---|---|
[BOJ] 11726 2×n 타일링 (0) | 2023.09.15 |
[BOJ] 18511 큰 수 구성하기 (0) | 2023.09.12 |
[BOJ] 15721 번데기 (1) | 2023.09.11 |
댓글