백준 1969 DNA Python 3

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

1969번: DNA

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1969.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def find_dna(dna, N, M):
    dis = 0
    answer = ""
    for i in range(M):
        cnt = {'A': 0, 'C': 0, 'G': 0, 'T': 0}
        for j in range(N):
            cnt[dna[j][i]] += 1
        answer += max(cnt.keys(), key=lambda x:cnt[x])
        dis += (sum(cnt.values())-cnt[answer[-1]])
    print(answer)
    print(dis)

input = sys.stdin.readline
N, M = map(int, input().split())
dna = list()
for _ in range(N):
    dna.append(input())
find_dna(dna, N, M)

---

풀이 과정

풀이 시간 41분

길이가 M인 N개의 DNA가 주어진다. 이 N개의 DNA와의 Hamming Distance가 가장 작은 DNA s를 구하는 문제이다.

여기서 주의해야할 점은 주어진 N개의 DNA끼리 Hamming Distance를 비교하는 문제가 아니라는 점이다.

이부분 이해를 잘못해서 문제 푸는 시간을 소요했다.

N개의 DNA와의 Hamming Distance가 가장 작은 새로운 DNA s를 구해야 한다.

각 위치의 뉴클레오티드 문자를 비교하는 것이기 때문에 s의 각자리를 결정할 때 Hamming Distance가 최소가 되는 선택을 함으로써 문제를 해결할 수 있다.

따라서 그리디 알고리즘을 적용하면 된다.

import sys
def find_dna(dna, N, M):
	#Hamming Distance의 합
    dis = 0
    #Hamming Distance가 가장 작으면서 사전순으로 가장 앞 선 정답 DNA
    answer = ""
    
    #각 위치의 뉴클레오티드 문자를 탐색
    for i in range(M):
    	#N개 문자열의 i번째 문자를 카운팅 -> 사전 순으로 뉴클레오티드 문자를 넣어준다
        cnt = {'A': 0, 'C': 0, 'G': 0, 'T': 0}
        for j in range(N):
            cnt[dna[j][i]] += 1
            
        #가장 적은 수의 뉴클레오티드 문자를 선택한다 -> 그게 둘 이상이라면 cnt 딕셔너리에 가장 먼저 정의된 key를 반환한다
        answer += max(cnt.keys(), key=lambda x:cnt[x])
        
        #정답 dna의 i번째 문자와 다른 개수를 카운팅
        dis += (sum(cnt.values())-cnt[answer[-1]])
        
    print(answer)
    print(dis)

input = sys.stdin.readline
N, M = map(int, input().split())
dna = list()
for _ in range(N):
    dna.append(input())
find_dna(dna, N, M)

#시간복잡도 = O(NM) -> O(n), 공간복잡도 = O(n)