BOJ 1969(python) : DNA
링크 : https://www.acmicpc.net/problem/1969
- 입력
첫줄에 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
7
첫째 줄 T T A T T
T4개, A1개 T출력 후 Hamming Distance +1
둘째 줄 A A A G A
A4개, G1개 A출력 후 Hamming Distance +1
...
예제입력 2
4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA
예제출력 2
ACGTACGTAA
6
...
마지막 줄 C G T A
갯수 다동일, 사전순 A 출력후 Hamming Distance +3
- NM 만큼의 탐색을 해도 최대 5만번 이니까 브루투포스 알고리즘 ( O(Nm) + 정렬 시간 )
설계
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA
-
2중포문을 돌려서 첫째 줄 A,C,G,T 을 비교
-
나온 Count 값이 큰 순서 + 사전 순으로 정렬, 출력
+) n크기 만큼의 정렬을 m번 수행 -
HamDistance 더하기
-
출력
import sys
n,m = map(int,sys.stdin.readline().split())
dnalist = [str(sys.stdin.readline().replace('\n','')) for i in range(n)]
dnadic = dict()
hamdistance = 0
for i in range(m):
for j in range(n):
if dnalist[j][i] not in dnadic:
dnadic[dnalist[j][i]] = 1
else:
dnadic[dnalist[j][i]] +=1
print(sorted(dnadic.items(),key=lambda x : (-x[1], x[0]))[0][0],end='')
hamdistance += n-max(dnadic.values())
dnadic.clear()
print()
print(hamdistance)
정렬함수 sorted 및 lambda사용법에 대해 알고 가기
sorted(dnadic.items(),key=lambda x : (-x[1], x[0]))
dnadic의 아이템들을 dnadic[1]의 값들의 역순으로 정렬한 후
x[0]의 값으로 사전순 정렬
Author And Source
이 문제에 관하여(BOJ 1969(python) : DNA), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cksgodl/BOJ-1969-DNA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)