[Silver IV] DNA - 1969

문제 링크

성능 요약

메모리: 34924 KB, 시간: 68 ms

분류

구현, 그리디 알고리즘, 문자열, 브루트포스 알고리즘

문제 설명

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개의 길이 M인 DNA s₁, s₂, ..., s_n가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 s₁의 Hamming Distance + s와 s₂의 Hamming Distance + s와 s₃의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

입력

첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

---

문제 풀이

문제 분석

이 문제는 N개의 DNA 문자열이 주어졌을 때, 이 N개의 DNA 문자열들과의 Hamming Distance의 합이 가장 작은 새로운 DNA 문자열 S를 찾는 것입니다. Hamming Distance는 길이가 같은 두 DNA 문자열에서 각 위치의 문자가 서로 다른 개수를 의미합니다. 만약 합이 가장 작은 DNA 문자열 S가 여러 개 있다면, 그 중 사전순으로 가장 앞서는 것을 출력해야 합니다. 최종적으로는 이 새로운 DNA 문자열 S와 그 때의 최소 Hamming Distance의 합을 출력합니다.

• 입력: 첫 줄에 DNA의 수 N (1,000 이하)과 각 DNA 문자열의 길이 M (50 이하)이 주어집니다. 다음 N줄에 길이가 M인 N개의 DNA 문자열이 주어집니다.
• 출력: 첫 줄에는 Hamming Distance의 합이 가장 작은 DNA 문자열 S를 출력하고, 둘째 줄에는 그 때의 최소 Hamming Distance 합을 출력합니다.

접근 방법

이 문제의 핵심은 Hamming Distance의 합을 최소화하는 것입니다. 특정 문자열 s와 N개의 입력 문자열 s_1, ..., s_N 간의 총 Hamming Distance는 sum(HammingDistance(s, s_i) for i in 1 to N) 입니다.

Hamming Distance의 정의를 생각해보면, 이는 각 위치(열)별로 독립적으로 계산하여 합산할 수 있습니다. 즉, s[j]와 s_i[j]가 다르면 해당 위치에서 1이 추가되고, 같으면 0이 추가됩니다. 따라서 총 Hamming Distance 합은 sum(sum(1 if s[j] != s_i[j] else 0 for i in 1 to N) for j in 0 to M-1) 로 표현할 수 있습니다.

이 식을 최소화하려면, 각 열 j에 대해 sum(1 if s[j] != s_i[j] else 0 for i in 1 to N) 값을 독립적으로 최소화하면 됩니다. 어떤 한 열 j에 대해서 s[j]를 결정할 때, N개의 DNA 문자열 s_1[j], s_2[j], ..., s_N[j] 중에서 가장 많이 등장하는 문자를 s[j]로 선택하는 것이 해당 열의 Hamming Distance를 최소화하는 방법입니다. 예를 들어, 어떤 열에 'A'가 5개, 'C'가 3개, 'G'가 2개 있다고 합시다 (총 10개 DNA).

• s[j]를 'A'로 선택하면, Hamming Distance는 'A'가 아닌 문자('C'와 'G')의 개수인 3 + 2 = 5가 됩니다. (이는 총 DNA 수 N - 'A'의 개수와 같습니다: 10 - 5 = 5)
• s[j]를 'C'로 선택하면, Hamming Distance는 5 + 2 = 7이 됩니다.
• s[j]를 'G'로 선택하면, Hamming Distance는 5 + 3 = 8이 됩니다.

따라서 각 열에서는 가장 많이 등장하는 문자를 s[j]로 선택해야 해당 열의 Hamming Distance를 최소화할 수 있습니다. 만약 가장 많이 등장하는 문자가 여러 개라면, 문제 조건에 따라 사전순으로 가장 앞서는 문자를 선택합니다. ('A' < 'C' < 'G' < 'T')

이러한 접근 방식은 그리디 알고리즘에 해당합니다. 각 열에서 지역적으로 최적의 선택을 하는 것이 전체 문제의 최적 해를 보장합니다.

구현 설명

주어진 파이썬 코드는 이 그리디 접근 방식을 그대로 구현합니다.

1. DNA 문자열 입력 및 저장

• n, m = map(int, input().split()): DNA의 수 N과 길이 M을 입력받습니다.
• arr = []: 모든 DNA 문자열을 저장할 리스트를 초기화합니다.
• for i in range(n): arr.append(list(input().strip())): N개의 DNA 문자열을 한 줄씩 읽어 list() 함수를 사용하여 문자 리스트로 변환한 후 arr에 추가합니다. 예를 들어, "ATGC"는 ['A', 'T', 'G', 'C']로 저장됩니다. 이렇게 하면 각 열(인덱스)에 접근하기 편리해집니다.

2. 각 열(위치)별 최적 문자 선택 및 Hamming Distance 합 계산

• answer_word = []: 최종 DNA 문자열을 구성할 문자들을 저장할 리스트입니다.
• answer_num = 0: 총 Hamming Distance 합을 저장할 변수입니다.
• for j in range(m):: M개의 각 열(j는 0부터 M-1까지)에 대해 반복합니다.
  • d = defaultdict(int): 현재 열 j에서 각 뉴클레오티드('A', 'C', 'G', 'T')의 등장 횟수를 세기 위한 딕셔너리를 초기화합니다.
  • for i in range(n): d[arr[i][j]] += 1: N개의 DNA 문자열(arr[i])을 순회하며, 각 문자열의 j번째 문자(arr[i][j])의 등장 횟수를 d 딕셔너리에 업데이트합니다.
  • for x,y in sorted(d.items(), key= lambda x:(-x[1],x[0]))::
    • d.items()는 딕셔너리의 (문자, 빈도수) 쌍들을 반환합니다.
    • key= lambda x:(-x[1],x[0]): 이 key 함수가 정렬의 핵심입니다.
      • -x[1]은 빈도수(y)의 음수 값을 의미합니다. 따라서 빈도수가 높은 것부터 (내림차순) 정렬됩니다.
      • x[0]은 문자 자체(x)를 의미합니다. 만약 빈도수가 같은 문자(예: 'A'와 'G'가 모두 최빈값)가 있다면, 알파벳 순서대로 (오름차순, 'A'가 'G'보다 먼저) 정렬됩니다.
    • 결과적으로 sorted() 함수는 가장 빈도수가 높은 문자를 첫 번째로, 빈도수가 같으면 사전순으로 가장 빠른 문자를 첫 번째로 오게 정렬합니다.
  • answer_num += n-y: 정렬된 결과의 첫 번째 (x,y) 쌍은 현재 열 j에 대해 최적으로 선택된 문자 x와 그 빈도수 y를 나타냅니다. n-y는 현재 열에서 x가 아닌 문자의 개수, 즉 현재 열의 최소 Hamming Distance입니다. 이를 answer_num에 더합니다.
  • answer_word.append(x): 선택된 문자 x를 answer_word 리스트에 추가합니다.
  • break: 가장 빈도수가 높은(또는 사전순으로 가장 빠른) 문자를 찾았으므로 더 이상 반복할 필요 없이 루프를 종료합니다.

3. 결과 출력

• print("".join(answer_word)): answer_word 리스트에 저장된 문자들을 합쳐 하나의 문자열로 만든 후 출력합니다. 이것이 문제에서 요구하는 최적의 DNA 문자열입니다.
• print(answer_num): 계산된 총 Hamming Distance의 합 answer_num을 출력합니다.

⏱복잡도 분석

• 시간 복잡도:

  • 입력 N과 M을 읽는 것은 O(1)입니다.
  • N개의 DNA 문자열을 arr에 저장하는 과정: 각 문자열은 M 길이이고 N번 반복하므로 O(N*M) 시간이 소요됩니다. strip() 및 list() 변환 과정도 문자열 길이에 비례합니다.
  • 주요 로직: for j in range(m) 루프는 M번 반복합니다.
    • 내부의 for i in range(n) 루프는 N번 반복하며 defaultdict에 문자의 빈도수를 업데이트합니다. 딕셔너리 접근 및 업데이트는 평균적으로 O(1)입니다. 따라서 이 부분은 O(N)입니다.
    • sorted(d.items(), ...): d 딕셔너리는 'A', 'C', 'G', 'T' 4가지 문자만 가질 수 있으므로 최대 4개의 항목을 가집니다. 상수 개수의 항목을 정렬하는 것은 O(1) (상수 시간)으로 간주할 수 있습니다.
  • 따라서 전체 시간 복잡도는 O(N*M + M * (N + 1))이며, 이를 간단히 하면 O(N*M) 입니다.
  • 제약 조건 (N=1000, M=50)을 고려할 때, 1000 * 50 = 50,000 연산으로 매우 효율적으로 동작합니다.

• 공간 복잡도:

  • arr: N개의 길이 M인 문자열을 저장하므로 O(N*M) 공간을 사용합니다.
  • d: defaultdict는 최대 4개의 (문자, 빈도수) 쌍만 저장하므로 O(1) 공간을 사용합니다.
  • answer_word: 길이 M인 최종 DNA 문자열을 저장하므로 O(M) 공간을 사용합니다.
  • 따라서 전체 공간 복잡도는 O(N*M) 입니다.
  • 제약 조건 (N=1000, M=50)을 고려할 때, 50,000개의 문자(또는 그에 해당하는 정수/포인터)를 저장하는 것으로 충분히 관리 가능한 메모리 양입니다.

핵심 포인트

1. 그리디 알고리즘 적용: N개의 DNA 문자열과의 Hamming Distance 합을 최소화하기 위해서는 각 열(위치)마다 독립적으로 최적의 문자를 선택하는 그리디 전략을 사용합니다. 한 열에서 가장 많이 등장하는 문자를 선택하는 것이 해당 열의 Hamming Distance를 최소화합니다.
2. 컬럼별 빈도수 계산: defaultdict를 활용하여 각 열에서 'A', 'C', 'G', 'T' 각 뉴클레오티드의 등장 횟수를 효율적으로 계산합니다. 이는 최빈 문자를 찾기 위한 필수 단계입니다.
3. 정렬을 통한 최빈값 및 사전순 처리: sorted(d.items(), key=lambda x: (-x[1], x[0])) 구문을 사용하여, 빈도수(-x[1]로 내림차순)를 기준으로 1차 정렬하고, 빈도수가 같을 경우 문자(x[0]로 오름차순)를 기준으로 2차 정렬함으로써 문제의 요구사항인 "최빈 문자 중 사전순으로 가장 앞서는 것"을 정확하게 찾아냅니다.

풀이 코드

import sys
from collections import defaultdict

input = sys.stdin.readline

n,m = map(int, input().split())

arr = []
for i in range(n):
    arr.append(list(input().strip()))

answer_word = []
answer_num = 0
for j in range(m):
    d = defaultdict(int)
    for i in range(n):
        d[arr[i][j]] += 1

    for x,y in sorted(d.items(), key= lambda x:(-x[1],x[0])):
        answer_num += n-y
        answer_word.append(x)
        break

print("".join(answer_word))
print(answer_num)