[백준] 1969번 DNA

실버5단계의 문제이다.

N개의 DNA가 주어지고, Hamming Distance가 가장 작게 나오는 DNA 서열을 구하는 문제이다.

 

이 문제는,

각각의 서열을 인덱스로 접근하여서 가장 많이 나온 알파벳을 추가하는 방식으로 문제를 해결했다.

 

처음에 문제를 끝까지 다 안읽어서 멀리까지 돌고 돌다가 왔다..ㅎㅎ

"그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다."

만약 DNA 서열들의 1번 인덱스가 A 1개, T 1개, G 1개, C 1개 있다고 했을 때 A를 추가해주면 되는데, 위에 문장을 안읽고 각각 넣어보고 다른 서열들과 비교해서 Hamming Distance가 가장 작은 것을 찾는 방식으로 풀다가 포기했다..ㅎ

 

오늘의 교훈문제 끝까지 읽자..^~^

 

해결코드

N, M = map(int, input().split())

DNAs = []
for n in range(N):
    DNAs.append(input())

min_sum = 0xffffffff
# target = []

# 길이가 M인 문자열을 돌면서 가장 알파벳이 많이 나온 것을 찾아서 조합한다.
result = ""
# 길이가 M이니까 앞에서부터 돌면서
for m in range(M):
    # 각각 알파벳의 개수를 세어준다.
    atgc = [[0, "A"], [0, "T"], [0, "G"], [0, "C"]]
    # 모든 DNA를 돌면서 해당 인덱스에 맞는 알파벳에 +1를 해준다.
    for dna in DNAs:
        if dna[m] == "A": atgc[0][0] += 1
        elif dna[m] == "T": atgc[1][0] += 1
        elif dna[m] == "G": atgc[2][0] += 1
        elif dna[m] == "C": atgc[3][0] += 1
    
    # 가장 많이 나온 알파벳부터 추가를 해본다.
    max_alphabet = ""
    maxV= -1
    for i in atgc:
        # print(type(i[0]), type(maxV))
        if i[0] > maxV:
            max_alphabet = i[1]
            maxV = i[0]
        elif i[0] == maxV:
            max_alphabet = i[1] if ord(i[1]) < ord(max_alphabet) else max_alphabet

    result += max_alphabet

dist = 0
for dna in DNAs:
    for m in range(M):
        if result[m] != dna[m]:
            dist += 1
print(result)
print(dist)