풀기실패 - 풀이 참고(pjok1122님)
문제
DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자를 따서 표현한다. 만약에 Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-Cytosine-Cytosine-Guanine-Adenine-Thymine로 이루어진 DNA가 있다고 하면, “TAACTGCCGAT”로 표현할 수 있다. 그리고 Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클오티드 문자가 다른 것의 개수이다. 만약에 “AGCAT"와 ”GGAAT"는 첫 번째 글자와 세 번째 글자가 다르므로 Hamming Distance는 2이다.
우리가 할 일은 다음과 같다. n개의 길이가 같은 DNA가 주어져 있을 때(이 DNA를 a1a2a3a4...이라고 하자) Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 a1의 Hamming Distance + s와 a2의 Hamming Distance + s와 a3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.
입력
첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.
출력
첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.
예제입력
5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT예제출력
TAAGATAC
7Note
처음에는 주어진 각 DNA를 비교해서 자신을 제외한 다른 DNA와 비교했을때 humming distance의 합이 가장 작은 DNA를 선택하는 줄 알았는데 아니었다. 뒤늦게 문제의 의미를 알아채고 다시 생각을 해보았다.
2차원 array를 만든다.- 각 열을 돌아가면서 어느 뉴클레오타이드가 가장 많이 나오는지 확인한다 --> 어떻게?
- 만약 갯수가 중복된다면 사전순으로 결정한다.
- 끝 열까지 다 돌고 만들어진
DNA로 각 행을 돌면서humming distance를 확인한다.
참고한 풀이
N,M = map(int,input().split())
dna = []
result =''
hd = 0
for i in range(N):
dna.append(input())
for i in range(M):
cnt = [0,0,0,0]
for j in range(N):
if dna[j][i] == 'A':
cnt[0] +=1
elif dna[j][i] =='C':
cnt[1] +=1
elif dna[j][i] == 'G':
cnt[2] +=1
elif dna[j][i] == 'T':
cnt[3] +=1
Max = max(cnt)
idx = cnt.index(Max)
if idx ==0:
result+='A'
elif idx==1:
result+='C'
elif idx==2:
result+='G'
elif idx==3:
result+='T'
hd += N - Max
print(result)
print(hd)- 굳이 2차원 array를 선언하지 않아도 2차원처럼 인덱싱이 가능하다.
- 가장 나오는 빈도가 높은 뉴클레오타이드를 어떻게 찾아야할지에서 막혔었는데 count list를 만들고 2차원 array에서 하는 것 처럼 열을 돌면서 카운트를 하면 된다.
max()로 최대값을 찾기.index(Max)로 최대값이 나온 index를 찾을 수 있다. 또한 값이 중복으로 있을 때에는 맨 처음 나온 index를 찾기 때문에 사전순이 되는 셈이다.- Humming distance는 한 열을 돌면서 뉴클레오타이드가 확정될 때마다
N-Max증가하게 된다.
