Baekjoon 백준 알고리즘 - DNA ( 1969 )

1. 문제 소개

• 구현 / 그리디 알고리즘 / 문자열 / 브루트포스 알고리즘 문제에 속한다.
• https://www.acmicpc.net/problem/1969

1969번: DNA

 

2. 코드

# 2개의 DNA 뉴클레오티드로부터 해밍디스턴스의 길이를 반환하는 함수
def get_hamming_distance(dna1,dna2,m):
    hamming_distance = 0

    for i in range(m):
        if dna1[i] != dna2[i]:
            hamming_distance += 1

    return hamming_distance

def get_test_case():
    input_str= input().split(" ")
    h,m = int(input_str[0]),int(input_str[1])
    dna_list = ['' for x in range(h)]
    for i in range(h):
        dna_list[i] = input()
    return h, m, dna_list

def solution():
    H,M,DNA_list = get_test_case()
    min_dna = ''

    for i in range(M):
        alphabet_count = [0 for x in range(26)] 
        for dna in DNA_list:
            ch = ord(dna[i])
            alphabet_count[ch % 65] += 1
        max_count = max(alphabet_count)
        org_ch = alphabet_count.index(max_count) + 65
        dna_char = chr(org_ch)
        min_dna += dna_char
    min_hamming_distance_sum = 0

    # 해밍디스턴스의 합을 구하기
    for dna in DNA_list:
        min_hamming_distance_sum+= get_hamming_distance(dna,min_dna,M)
    print(f"{min_dna}\n{min_hamming_distance_sum}")

if __name__ == '__main__':
    solution()

 

 

3. 코멘트

• 문제해결의 전략은 아래와 같다.
  • 해밍 디스턴스의 최소가 되는 DNA 문자열 = 입력 문자열 { DNA s(1)..s(n) } 에서 자리 별 최대 중복 문자로 조합된 문자열  
  • 최대 중복수가 같거나 없다면 사전 순 가장 처음으로 오는 영어 문자 배치
  • 문자열 카운팅은 배열과 아스키코드를 이용해서 구하기
• 처음에 예제 입력에서 해답인 DNA s 를 구하는 것으로 생각하고 구현했다가 시간을 버렸다. 
• 역시 문제는 꼼꼼히 읽고 해석해야 한다.. 그리고 오늘 같이 날씨가 너무 좋은 날에 스터디에 참여한 스터디원 들이 고맙다.