1969번: DNA

문제 출처 : https://www.acmicpc.net/problem/1969

1969번: DNA

언어 : Kotlin

 

문제 설명 :

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

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT	TAAGATAC 7
4 10 ACGTACGTAC CCGTACGTAG GCGTACGTAT TCGTACGTAA	ACGTACGTAA 6
6 10 ATGTTACCAT AAGTTACGAT AACAAAGCAA AAGTTACCTT AAGTTACCAA TACTTACCAA	AAGTTACCAA 12

 

풀이 : 

문제 이해하는게 가장 어려웠다.

아래의 표는 예시 1번을 토대로 문제를 풀이한 것이다.

 

T	A	T	G	A	T	A	C
T	A	A	G	C	T	A	C
A	A	A	G	A	T	C	C
T	G	A	G	A	T	A	C
T	A	A	G	A	T	G	T
↓	↓	↓	↓	↓	↓	↓	↓
T	A	A	G	A	T	A	C
1	1	1	0	1	0	2	1

 

Bold 표시된 검은 글씨가 모여지면 TAAGATAC가 나온다.

붉은 글씨의 개수가 전부 합해지면 7이 나온다.

 

즉, 입력받은 DNA를 가로행으로 푸는게 아니라 세로열로 푸는게 핵심이다.

Hamming Distance의 합이 가장 적은 DNA는 세로열 중 가장 많이 나온 문자들로 구성된 문자열을 반환하라는 것이다.

그 Hamming Distance의 합을 출력하시오. 는 세로열 중 가장 많이 나온 문자를 제외한 문자들 개수의 합을 말하는 것.

 

import java.io.BufferedWriter
import java.io.OutputStreamWriter

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (n, m) = readLine().split(" ").map { it.toInt() }
    val dna = Array(n) { readLine() }
    var newDna = ""
    var sum = 0
    for (i in 0 until m) {
        val st = StringBuilder()
        for (j in 0 until n) { st.append("${dna[j][i]}") }
        val key = st.groupingBy { it }.eachCount().maxWith(compareBy<Map.Entry<Char, Int>> { it.value }.thenByDescending { it.key }).key
        sum += st.groupingBy { it }.eachCount().filter { it.key != key }.values.sum()
        newDna += key
    }
    bw.appendLine(newDna).append("$sum")
    bw.flush()
    bw.close()
}