[BaekJoon] "완전탐색" - 백준 1969번 문제 : DNA

[문제 설명]

https://www.acmicpc.net/problem/1969

1969번: DNA

 

DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있음 (A, T, G, c)

Hamming distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클레오티드 문자가 다른 것의 개수

만약에 AGCAT, GGAAT는 첫번재, 세번째 글자가 다르므로 Hamming Distance = 2

N개의 길이 M인 DNA가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA를 구하는 것

 

 

[해결 로직]

- 처음에는 입력으로 주어지는 문자열들 사이사이를 비교하는건가? 생각했었음

- 근데 그게 아니라, 쟤네랑 어떤 문자열 S랑 비교했을 때 변경 수가 가장 적어야하는 S를 찾아야 하는 거였음

- 그래서 한 열 씩 검사하면서 A,C,G,T의 개수를 카운팅함

- 제일 많은게 T라면 S의 첫번째 열의 문자는 T가 되는거임.

- 이게 무슨 말이냐면 제일 많이 분포 되어 있는 문자열로 정해놔야 제일 변경횟수가 적을 것이기 때문

- 변경 횟수는 각 열 별로 n - (max(카운팅수))를 계속 더하면 최소의 변경 횟수 합임

 

[Solution 코드]

n,m = map(int, input().split())
ary= []
result = ''
for i in range(n):
    tmpary = list(map(str, input()))
    ary.append(tmpary)
total = 0
for i in range(m): ## 문자열 길이
    cnt = [0,0,0,0] ## A,C,G,T
    for j in range(n):
        if ary[j][i] == 'A':
            cnt[0] += 1
        elif ary[j][i] == 'C':
            cnt[1] += 1
        elif ary[j][i] == 'G':
            cnt[2] += 1
        elif ary[j][i] == 'T':
            cnt[3] += 1
    idxcnt = cnt.index(max(cnt))
    if idxcnt == 0:
        result += 'A'
    elif idxcnt == 1:
        result += 'C'
    elif idxcnt == 2:
        result += 'G'
    elif idxcnt == 3:
        result += 'T'
    total += n - max(cnt)
    
print(result)
print(total)
## https://yuna0125.tistory.com/112

 

문제를 처음에 이해하기 어려웠당

막상 이해하니 오케이 ! 

근데 완전 탐색이라고 해놓고 그냥 DFS 이런게 아니라 진짜 완전 탐색 느낌이당

그니깐 너무 알고리즘 이름에 연연하지 말길 !