[백준] 1969 dna
[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 s1, s2, ..., sn가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 s1의 Hamming Distance + s와 s2의 Hamming Distance + s와 s3의 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개의 문자(또는 그에 해당하는 정수/포인터)를 저장하는 것으로 충분히 관리 가능한 메모리 양입니다.
핵심 포인트
- 그리디 알고리즘 적용: N개의 DNA 문자열과의 Hamming Distance 합을 최소화하기 위해서는 각 열(위치)마다 독립적으로 최적의 문자를 선택하는 그리디 전략을 사용합니다. 한 열에서 가장 많이 등장하는 문자를 선택하는 것이 해당 열의 Hamming Distance를 최소화합니다.
- 컬럼별 빈도수 계산:
defaultdict를 활용하여 각 열에서 'A', 'C', 'G', 'T' 각 뉴클레오티드의 등장 횟수를 효율적으로 계산합니다. 이는 최빈 문자를 찾기 위한 필수 단계입니다. - 정렬을 통한 최빈값 및 사전순 처리:
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)