[백준/Python] 1969번 DNA

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

1969번: DNA

 

문제분석

DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클레오티드 문자가 다른 것의 개수이다. Hamming Distance의 합이 가장 작은 DNA와 Hamming Distance의 합을 구하라.

조건 1. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

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

 

코드

n, m = map(int, input().split())
arr = [str(input()) for i in range(n)]

result = ''
count = 0

for i in range(m):
    DNA = [0, 0, 0, 0]  # A,T,G,C

    # n개의 DNA 중에서 가장 많이 나온 뉴클레오티드 구하기
    for j in range(n):
        if arr[j][i] == 'A':
            DNA[0] += 1
        elif arr[j][i] == 'C':
            DNA[1] += 1
        elif arr[j][i] == 'G':
            DNA[2] += 1
        elif arr[j][i] == 'T':
            DNA[3] += 1

    idx = DNA.index(max(DNA))

    # Hamming Distance의 합이 가장 작은 DNA 구하기
    if idx == 0:
        result += 'A'
    elif idx == 1:
        result += 'C'
    elif idx == 2:
        result += 'G'
    elif idx == 3:
        result += 'T'

    # Hamming Distance 계산하기
    count += n - max(DNA)

print(result)
print(count)

 

문제풀이

1. N과 M 그리고 N개의 DNA를 차례로 입력받는다.

2. Hamming Distance의 합이 가장 작은 DNA의 결과를 저장할 result와 Hamming Distance의 합을 저장할 count를 선언한다.

3. N개의 DNA에 각각 M개의 뉴클레오티드가 있는데, M개의 위치에 가장 많이 나오는 뉴클레오티드를 구하기 위해서 DNA 배열을 만든다. (Hamming Distance의 합이 가장 작은 DNA란, 각 위치의 뉴클오티드 문자가 가장 많이 나오는 걸 구하는 것과 같다.)

4. 이중 for문으로 N개의 DNA에 M개의 뉴클레오티드를 확인하면서, 나온 뉴클레오티드를 if문으로 DNA 배열에 +1을 하면서 체크한다.

5. max함수로 DNA함수에서 가장 큰 값을 구하고, index함수로 해당 값의 인덱스 번호를 구해서 idx에 저장한다.

6. 구한 idx에 따라서 result에 A, C, G, T를 추가하면서 Hamming Distance의 합이 가장 작은 DNA을 구한다.

7. Hamming Distance의 합을 구하기 위해서, max함수로 DNA함수에 가장 큰 값을 구한 것을 사용한다. 전체 DNA의 개수인 N에서 가장 많이 나왔던 뉴클레오티드의 개수를 빼면, 위해서 구했던 Hamming Distance의 합이 가장 작은 DNA와 다른 뉴클레오티드를 가지고 있는 개수를 구할 수 있다.