[백준 1969] DNA

앞에서부터 차례로 살펴가면서 모든 경우의 수를 확인해봅시다.

N개의 DNA 문자열이 주어질 것이고 각각의 길이는 M이라 명시되어 있습니다.
이때, 우리의 목표는 모든 DNA 문자열과 비교했을때
글자 차이의 합이 가장 적게 나는 DNA 문자열 을 만드는 것입니다.

주목할만한 아이디어는 다음과 같습니다.

DNA 문자열의 동일한 위치의 글자들을 모두 모아 비교한 다음
더 많은 개수의 문자를 선택하면 된다.

예를 들면, 5개의 DNA 문자열의 첫 글자들이 T,T,A,T,T라고 한다면
차이를 가장 적게 하기 위해서는 다수인 T를 선택하면 되는 것입니다.
단, 이를 위해서는 N개의 문자열에서 동일한 위치의 글자들을
앞에서부터 차례로 하나하나 살펴보아야 합니다.

따라서, DNA라는 하나의 리스트를 만든 다음 N번 동안 입력되는 문자열을 append합니다.
또한, 동일한 위치의 글자들을 모아놓고 비교할 temp라는 리스트를 만듭니다.
이 temp를 set 자료형으로 만들면 중복된 요소가 사라지기 때문에
글자의 종류를 쉽게 알아낼 수 있습니다.
가장 다수인 글자의 개수와 종류를 저장할 변수들을 각각 0과 ‘Z’로 초기화해둡니다.
그 후에, 아까의 set 안에 있는 요소들의 개수를 각각 파악하며
가장 다수인 글자의 종류와 개수를 저장합니다.
개수가 같다면 사전 순으로 앞선 것을 출력하라는 조건이 있으므로
if 문과 ord()를 통해 ASCII code를 비교하여 더 작은 ASCII code를 가지는 글자를 저장합니다.
그렇게 길이 M을 모두 순회하면 최종적인 답이 출력됩니다.

예시를 보면 더 쉽게 이해할 수 있습니다.

TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT 가 입력되었을 때,
인덱스 0인 글자들을 temp = [‘T’,’T’,’A’,’T’,’T’]로 모아둡니다.
dnatype = set(temp) = {‘T’, ‘A’}로 중복을 제거하고 나면 글자의 종류를 파악할 수 있습니다.
우리는 이 글자들 중 가장 개수가 많은 글자를 알아내야 하는 것입니다.
따라서 개수와 글자를 저장할 maxnum, maxdna를 각각 0과 ‘Z’로 초기화합니다.
그 후 for문과 if문을 통해 다수를 차지하는 글자의 개수와 종류를 저장합니다.
이 경우에는 ‘T’가 4개, ‘A’가 1개이므로 더 많은 글자인 T를 ans에 저장하면 되는 것입니다.
그리고, 차이 또한 답으로 출력해야하므로 5개의 글자 중 T가 아닌 A 1개를 anscnt에 저장하면 됩니다.
이렇게 하면 1턴이 끝납니다.
이제 다음 턴으로 넘어가 인덱스가 1인 글자들을 파악하여
temp = [‘A’,’A’,’A’,’G’,’A’]로 하여 이전과 똑같이 하면 됩니다.
이 과정을 글자의 길이인 M번 반복하면 최종적인 DNA 문자열과 차이가 나오게 됩니다.

문제 : 백준 1969 - DNA