1969-백준-DNA

1. 문제 출처

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

1969번: DNA

2. 풀이

그리디 알고리즘을 이용한 문제이다..

힌트에 브루투포스 알고리즘도 적혀있던데 왜일까??

hamming_distance 구하는 과정이 모든 dna와 연산해야 해서 그런가?

# 입력
n,m = map(int,input().split())
dnas = []
for _ in range(n):
    dnas.append(input())

# 구한 결과의 hamming_distance의 합을 구하는 함수
def get_hamming_distance(a):
    distance = 0
    for dna in dnas:
        for idx in range(m):
            if dna[idx] != a[idx] :
                distance +=1
    return distance

# 그리디 알고리즘을 이용하여 dna구하기
def get_dna_greedy():
    #dna 뉴클리오드? 값 
    dna_feature = ["A","C","G","T"]
    result = ""
    # 각 dna당 해당 자리에 사용된 뉴클리오드 값의 총합
    most_used = [[0 for _ in range(4)] for _ in range(m)]
    for dna in dnas:
        for idx in range(len(dna)):
            most_used[idx][dna_feature.index(dna[idx])] +=1
    # 각 자리별 가장 많이 사용된 뉴클리오드를 해당 자리에 사용하는 dna를 만든다.
    # 이미 사전순으로 dna_feature를 정렬하였기에 사전순으로 하려면 
    for i in range(m):
        feature = ""
        used_count = 0
        for j in range(4):
            # 기장 큰값을 넣어준 후 most_used[i][j]== used_count라는 조건은 무시하면 된다. 
            if most_used[i][j] > used_count:
                used_count = most_used[i][j] 
                feature = dna_feature[j]
        result+=feature
        
        
    print(result)
    print(get_hamming_distance(result))
    
        
get_dna_greedy()