그리디알고리즘(DNA/S5)

○문제
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 ... 의 합이 최소가 된다는 의미이다.

 

 

○풀이 
입력 -

6 10

출력 - 

ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

n,m = map(int, input().split()) # 앞의 글자는 n, 뒤의 글자는 m으로 할당됨.
arr = []
result = ""
count = 0
for _ in range(n): # n번 loop을 돌면서 input을 arr에 append
arr.append(list(map(str, input())))

for j in range(m):
  dic = {"A" : 0,"C" : 0,"G" : 0,"T" : 0}
  key = dic.keys()
  for i in range(n):
    for k in key:
      if arr[i][j] == k:
        dic[k] = dic[k] + 1

  # 딕셔너리의 최대값
  r = format(max(dic, key=dic.get))
  result += r

  for z in key:
    if z != r:
      count += dic[z] 

print(result)
print(count)

 

○느낀점
푸는것보다 문제를 이해하는데 한참 걸린 문제로  A, C, G, T 중 가장 많이 나오는 알파벳을 뽑아 배열을 만들고 뽑은 알파벳을 제외한 다른 알파벳의 수를 구하는 문제였다. 특히 이번 문제에서 알파벳 수가 같을 경우 사전순으로 알파벳을 뽑게 되어있는데 딕셔너리가 순서를 기억하고 있어 같은 최댓값이어도 앞에 선언된 키를 가져오는 것을 확인할 수 있었다.