BOJ 1969(python) : DNA

링크 : https://www.acmicpc.net/problem/1969

---

• 입력
  첫줄에 DNA의 수 N과 문자열의 길이 M 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.
  

• 출력
  첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오.
  그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

---

예제입력 :
5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

예제출력 :
TAAGATAC
7

첫째 줄 T T A T T 
T4개, A1개 T출력 후 Hamming Distance +1
둘째 줄 A A A G A
A4개, G1개 A출력 후 Hamming Distance +1
...

예제입력 2
4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA

예제출력 2
ACGTACGTAA
6

...
마지막 줄 C G T A
갯수 다동일, 사전순 A 출력후 Hamming Distance +3

---

• NM 만큼의 탐색을 해도 최대 5만번 이니까 브루투포스 알고리즘 ( O(Nm) + 정렬 시간 )

설계
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA

1. 2중포문을 돌려서 첫째 줄 A,C,G,T 을 비교

2. 나온 Count 값이 큰 순서 + 사전 순으로 정렬, 출력
   +) n크기 만큼의 정렬을 m번 수행

3. HamDistance 더하기

4. 출력

import sys

n,m = map(int,sys.stdin.readline().split())

dnalist = [str(sys.stdin.readline().replace('\n','')) for i in range(n)]
dnadic = dict()
hamdistance = 0
for i in range(m):
    for j in range(n):
        if dnalist[j][i] not in dnadic:
            dnadic[dnalist[j][i]] = 1
        else:
            dnadic[dnalist[j][i]] +=1
    print(sorted(dnadic.items(),key=lambda x : (-x[1], x[0]))[0][0],end='')
    hamdistance += n-max(dnadic.values())
    dnadic.clear()
print()
print(hamdistance)

정렬함수 sorted 및 lambda사용법에 대해 알고 가기

sorted(dnadic.items(),key=lambda x : (-x[1], x[0]))

dnadic의 아이템들을 dnadic[1]의 값들의 역순으로 정렬한 후
x[0]의 값으로 사전순 정렬