BOJ-1969 DNA Swift

문제

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

내가 푼 풀이

- 주어진 문자열들의 열들을 비교해가며, 가장 많은 문자를 따온다.

- 만약 해당 열에 여러개의 문자의 수가 같다면, 사전순으로 앞에 있는 문자를 따온다.

- Hamming Distance는 해당 문자와 다른 문자의 갯수다. 

- 문자를 따올때, 해당문자와 다른 문자의 개수를 더해주면 주어진 문자열들과 Hamming Distance의 합이 가장 작은 DNA가 되고,

그 합이 이전에 더해진 수와 같다.

 

코드로 구현하면 다음과 같다.

 

import Foundation

let input = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [[String]]()
var str = ""
var hd = 0

// 문자열 입력
for i in 0..<input[0] {
    arr.append(Array(readLine()!).map{String($0)})
}

// 주어진 문자열의 열을 모두 비교
// 문자와 문자의 개수를 구한다.
// 문자를 배열에 저장해 오름차순으로 정렬하면 0번째 원소가 사전순으로 가장 앞선다.
// 해당 문자와 다른문자의 개수를 더해가면 주어진 문자열들과 Hamming Distance의 합이 최소가 된다.
for i in 0..<input[1] {
    var dict = [String: Int]()
    for j in 0..<input[0] {
        if dict[arr[j][i]] == nil {
            dict[arr[j][i]] = 1
        } else {
            dict[arr[j][i]]! += 1
        }
    }
    var hdNum = 0
    var s = [String]()
    for (key,value) in dict {
        if value == dict.values.max()! {
            hdNum = input[0] - value
            s.append(key)
        }
    }
    s.sort{ $0 < $1}
    str += s[0]
    hd += hdNum
}

print(str)
print(hd)