[백준] 1969번 DNA - 파이썬

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

1969번: DNA

 

풀이

Hamming Distance는 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클오티드 문자가 다른 것의 수이다.

이 문제에서 뉴클오티드 문자는 A, T, G, C 만 주어진다. Hamming Distance가 최소가 되는 문자를 찾으려면 가장 각 위치의 문자는 겹치는 부분이 적어야한다. 특히 문제에 나왔듯이 만약 겹치는 개수가 동일한 문자가 두 개 이상 나올시에는 사전적 우선순위인 문자를 고른다. TAGC변수에 뉴클오티드 문자를 사전순으로 정리해서 담아둔다. 추가로 TAGC_cnt에 겹치는 개수를 적어놓을 리스트를 만들어준다. 이중 for문을 통해 어떤 문자가 가장 많이 나왔는지 계산한 뒤 answer 변수에 가장 많이 나온 문자를 추가해준다.

# 1969번 DNA

N, M = map(int, input().split())
DNA = []
TAGC = ['A', 'C', 'G', 'T']
answer = ''
cnt = 0
for i in range(N):
    DNA.append(input())

for k in range(M):
    TAGC_cnt = [0, 0, 0, 0]
    for j in range(N):
        if DNA[j][k] == 'A':
            TAGC_cnt[0] += 1
        elif DNA[j][k] == 'C':
            TAGC_cnt[1] += 1
        elif DNA[j][k] == 'G':
            TAGC_cnt[2] += 1
        elif DNA[j][k] == 'T':
            TAGC_cnt[3] += 1
    word = max(TAGC_cnt)
    answer += TAGC[TAGC_cnt.index(word)]
    cnt += (N - word)

print(answer)
print(cnt)