DNA
면접 대비시간 제한2초메모리 제한128 MB
길이 M인 DNA 문자열 N개가 주어질 때 전체 해밍 거리의 합을 최소화하면서 사전순으로 가장 작은 문자열을 구하고 그 최소 거리를 출력합니다.
문제
DNA는 A, C, G, T 네 종류의 뉴클레오타이드 문자로 표현할 수 있다. 길이가 같은 두 DNA 문자열의 Hamming Distance는 같은 위치에 있는 문자가 서로 다른 위치의 개수이다.
길이가 M인 DNA 문자열 N개 s_1, s_2, ..., s_N이 주어진다. 길이가 M인 DNA 문자열 S를 하나 골라, S와 모든 입력 문자열 사이의 Hamming Distance 합을 최소로 만들려고 한다. 즉, d(S, s_1) + d(S, s_2) + ... + d(S, s_N)이 최소가 되는 S를 구해야 한다. 가능한 문자열이 여러 개라면 사전순으로 가장 앞서는 문자열을 선택한다.
입력
첫째 줄에 DNA 문자열의 개수 N과 각 문자열의 길이 M이 주어진다. 둘째 줄부터 N개의 줄에는 길이가 M인 DNA 문자열이 하나씩 주어진다.
N은 1 이상 1,000 이하이고, M은 1 이상 50 이하이다. 각 DNA 문자열은 문자 A, C, G, T로만 이루어져 있다.
출력
첫째 줄에 Hamming Distance 합이 최소가 되는 DNA 문자열을 출력한다. 그러한 문자열이 여러 개라면 사전순으로 가장 앞서는 문자열을 출력한다.
둘째 줄에는 그 최소 Hamming Distance 합을 출력한다.