Greedy(15)_DNA(1969)

작성일 | In

BJO 1969 DNA

Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 DNA 글자가 다른 것의 개수를 뜻한다.

n개의 길이가 같은 DNA가 주어졌을 때, Hamming Distance의 합이 가장 작은 DNA s를 구한다.

문제이해

  1. 우선 각 문자열의 길이만큼 다 입력 받는다.
  2. 각 문자열 중 가장 횟수가 많은 것을 뽑아서 s를 만들고
    • 이 때, 횟수가 겹치는 게 있다면 알파벳 순서가 더 먼저 나오는 것을 고른다.
  3. 구한 s와 각 문자열의 차이의 합을 구한다.

코드


import sys
N, M = map(int, sys.stdin.readline().split())

arr = []
for i in range(N):  # 2차원 리스트에 담아서
    arr.append(list(sys.stdin.readline().rstrip()))
result = []
string = ""
H_sum = 0
for j in range(M):
    count = [0, 0, 0, 0]
    for i in range(N):
        if(arr[i][j] == 'A'):
            count[0] += 1
        elif(arr[i][j] == 'C'):
            count[1] += 1
        elif(arr[i][j] == 'G'):
            count[2] += 1
        else:
            count[3] += 1
    # 리스트에서 가장 큰 값 구해서 M과 빼주고 H_sum에 누적
    maxChar = max(count)
    H_sum += N-maxChar
    # 리스트에서 가장 큰 값 인덱스 가져오기
    T = count.index(maxChar)

    if(T == 0):
        string += "A"
    elif(T == 1):
        string += "C"
    elif(T == 2):
        string += "G"
    else:
        string += "T"
print(string)
print(H_sum)

주의해야할 것.

리스트에서 가장 큰 값 구한 뒤 N과 빼준 다음에, 그 값을 누적해주면 hamming Distance를 구할 수 있다.

참고자료

0%