[Python] 백준(BOJ): 1969 DNA

문제

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

1969번: DNA

---

풀이

문자열을 순회하며 각 위치에서([0,m)) 가장 많이 사용된 물질(A, C, G, T)를 구하고, 그에 따른 hamming distance의 누적합을 구하면 된다. Greedy 보다는 Brute-Force에 가까운 것 같다.

 

1. 입력받은 DNA를 사전순으로 정렬
2. 입력받은 DNA에 대해 for loop를 수행하며 최다 빈출 염기 서열을 구함
3. hamming distance의 누적합을 구하는 for loop 수행

n, m = map(int, input().split())

data = []
for i in range(n):
    data.append(input())

data.sort()

dna = ''
# n: 주어지는 문자열 갯수
# m: 문자열의 길이
for y in range(m):
    value = {'A':0, 'C':0, 'G':0, 'T':0}
    for x in range(n):
        acgt = data[x][y]
        value[acgt] += 1
    dna += max(value, key=value.get)

answer = 0
for x in range(n):
    for y in range(m):
        if dna[y] != data[x][y]:
            answer += 1

print(dna)
print(answer)