[완전 탐색] 백준 1969번 (파이썬) : DNA

우선 위 문제 같은 경우에는 문제를 해석하는 것이 어려웠습니다.

특히 문제에서 정의하는 hamming distance를 밑의 예시 출력과 비교했을 때 제가 이해한 것과 맞지 않아 힘들었습니다.

여러 블로그를 통해 hamming distance를 찾아본 결과 결론은 다음과 같습니다.

 

해밍 거리는 특정 개수의 문자열이 같아지게 하기 위해 바꿔야 하는 문자의 수를 의미합니다.

예를 들어 AAA와 ATA라는 문자열이 있을 때 해밍 거리는 T를 A로만 바꾸면 두 문자열이 완전히 같아지기 때문에 가운데에서 해밍 거리가 1 발생한다고 할 수 있습니다.

그렇다면 문자열이 2개 이상일 때는 모든 문자열의 길이가 같다는 가정 하에 이들을 인덱스 별로 값을 비교하여 가장 빈도수가 높은 문자를 기준으로 해밍 거리가 발생하는 것입니다. 

예를 들어 AAA, AAC, ACC가 있으면 0번째는 모두 같으니 해밍 거리는 0이고 문제에서 요구하는 출력은 A, 1번째는 A가 2개 C가 1개이기 때문에 C 1개만 바꾸면 되므로 해밍 거리는 1 출력은 A, 마지막은 전과 반대로 C가 하나 더 많아서 해밍 거리는 1 출력은 C가 됩니다. 

결과적으로 출력은 AAC와 2가 나와야 올바르다는 것입니다.

 

이렇게 문제의 이해를 마친 후 코드에 대해 살펴보겠습니다.

n, m = map(int, input().split())
arr = []

for _ in range(n):
  arr.append(input())

ham = 0
result = ''

for i in range(m):
  a, t, c ,g = 0, 0 ,0 ,0
  for j in range(n):
    if arr[j][i] == 'A':
      a += 1
    elif arr[j][i] == 'T':
      t += 1
    elif arr[j][i] == 'C':
      c += 1
    elif arr[j][i] == 'G':
      g += 1

  if a == max(a, t, c, g):
    result += 'A'
  elif t == max(a, t, c, g):
    result += 'T'
  elif c == max(a, t, c, g):
    result += 'C'
  elif g == max(a, t, c, g):
    result += 'G'
    
  ham += n - max(a,t,c,g)

print(result)
print(ham)

먼저 문제의 출력 요구대로 n과 m은 map, split을 사용하여 int를 공백을 기준으로 한 줄에 입력받아줍니다.

 

그다음 DNA의 모든 줄의 입력을 받아줄 arr을 생성합니다. 일단 빈 배열을 만들어 for문을 이용하여 줄의 수만큼 배열을 생성합니다. 

밑에는 최종 결과를 담을 문자열 result와 해밍 거리에 해당하는 ham을 선언합니다. 

 

가장 중요한 for문입니다. 

첫 번째 for문의 range는 m으로 설정합니다. 이유는 그래야 DNA의 길이만큼 즉, 인덱스의 개수만큼 문자열을 보면서 해밍 거리를 계산할 것이기 때문입니다. 

첫 번째 for문 안에는 일단 매 인덱스 비교마다 초기화되는 A, T, C, G의 개수를 선언합니다.

 

다음은 두 번째 for문입니다. 우리는 하나의 DNA가 아니라 생성한 모든 DNA를 인덱스마다 비교할 것이기 때문에 2차원 배열로 변환하여 세로로 값을 비교하게 해 줍니다.

 

마지막은 한 인덱스씩 비교를 할 때마다 해밍 거리와 결과 DNA가 하나씩 나오기 때문에 if문은 두 번째 for문 밖에 선언합니다. 일단 결과 DNA에 해당하는 것은 각 인덱스마다 가장 빈도수가 높은 문자는 반환하는 것이기 때문에 if-elif-else로 인덱스마다 최댓값을 찾은 후 이를 result에 추가하는 작업을 합니다.

 

ham도 마찬가지로 한 인덱스 비교가 끝날 때마다 결정되기 때문에 if문과 같은 자리에 넣어줍니다.

ham은 n 즉 DNA의 개수에서 가장 빈도수가 높은 문자를 빼야 하기 때문에 위와 같이 식을 작성해 줍니다.