[백준 그리디] 1969 DNA

🥕 [ 백준 1969 ] DNA

문제 링크

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

1969번: DNA

 

🍒 문제 분석

길이 M짜리 DNA 갯수가 N개 주어진다.

주어진 DNA 들과 가장 거리가 가까운 DNA를 구한다.

거리는 각 자리수에 대해서 다른 DNA와 다른 것 만큼의 갯수를 의미한다.

 

가령, ABC, ACC 에 대한 ABB 가 갖는 거리는 0+1+2 = 3 이다.

 

🥑 코드

import sys
# N 은 DNA 갯수, M은 DNA 길이
N, M = map(int,sys.stdin.readline().split())
mylist = [sys.stdin.readline().strip() for _ in range(N)]

# 각 자리만 따서 이중 리스트 만듬
# 가령 ABCD, AABD 있으면, 각 자리 따서 [[A,A],[B,A],[C,B],[D,D]] 만드는 식
l = [[mylist[i][j] for i in range(N)] for j in range(M)]

# 가장 많은 count 가진 철자 뽑아보자.
anschar = ''
hamming = 0
for i in range(M):                     # DNA 길이 만큼
    max_cnt = 0                        # 각 자리에서 가장 많은 철자의 갯수를 뽑기 위해 선언 
    char = ''                          # 가장 많은 철자가 뭔지 저장하기 위해 선언
    for j in range(N):
        cnt = l[i].count(l[i][j])
        if max_cnt < cnt:              # 가장 많은 철자가 뭔지 찾고, 갯수를 센다.
            max_cnt = cnt
            char = l[i][j]
        elif max_cnt == cnt:           # 가장 많은 철자가 두개 이상 나올 경우,
            if char > l[i][j]:         # 사전적 순서가 작은거 하나만 저장
                char = l[i][j]
    anschar += char                    # 철자들을 합친다.
    hamming += N - max_cnt             # hmming 거리 또한 계산할 수 있다.

print(anschar)
print(hamming)

 

🍓 내 해결 과정

1. mylist 에 각 DNA를 요소로 받았다.

2. l 에 각 DNA 의 철자 자리들을 요소로 받는 이중 리스트를 만들었다.

가령 [ABC,BCD] 가 mylist라면, [ [ A, B ], [ B, C ], [ C, D ] ] 가 l 이다.

3. l[i] 의 요소들을 각각 카운트해서 가장 카운트가 높은 철자를 따로 뽑았다.

4. 만약 가장 높은 카운트의 철자가 2개 이상이라면, 사전적으로 더 작은 값을 뽑았다.

5. 뽑은 철자들을 합쳐 프린트 하였다.

6. 겸사겸사 hamming distance 계산은 덤 

 

일일히 다 검사 했기 때문에 내 풀이는 그리디 라기 보다는 브루트포스에 가까울 것 같다.

걸린 시간 : 596ms

 

🌽 다른 사람 코드

백준에서 다른 분 코드를 참고해서 다시 써봤다.

( max_char이라 선언하고 max_chr 을 써서 런타임 에러 Name error 걸렸는데 왜 걸렸는지 몰라서 한참 걸렸었다. 하 )

 

풀이 과정은 나랑 같은데, 다만 dictionary를 활용한 코드가 있어 나도 딕셔너리로 해봤다.

 

import sys
N, M = map(int,sys.stdin.readline().split())
mylist = [sys.stdin.readline().rstrip() for _ in range(N)]

ans_chr = ''
ans_distence = 0

for i in range(M):                              # 각 자리마다 비교
    dic = dict()
    dic['A'],dic['T'],dic['G'],dic['C'] = 0, 0, 0, 0
    
    for j in range(N):
        dic[mylist[j][i]] += 1                  # 딕셔너리에 철자별 갯수가 저장 되었다.
    
    max_cnt = 0
    max_char = ''
    for k in dic:
        if max_cnt < dic[k]:
            max_cnt = dic[k]                   # 가장 많은 철자의 갯수를 저장
            max_char = k                       # 가장 많은 철자에 해당하는 철자를 저장
        elif max_cnt == dic[k]:                # 가장 많은 철자가 2개 이상이면, 사전적 순서 우선
            if max_char > k:
                max_char = k
    ans_chr += max_char                        # 구한 철자를 답에 합쳐나간다.
    ans_distence += N - max_cnt                # distence 계산

print(ans_chr)
print(ans_distence)

 

걸린시간 76ms

 

각 자리 철자 중에서, 가장 많은 철자가 무엇인지 찾을 때,

딕셔너리는 A, T, G, C 만 방문하면 되므로 속도가 엄청나게 빨라진것 같다.

 

🍉 깨달은 점 및 정리

딕셔너리를 통해 각 요소들의 갯수를 더 빠르게 비교할 수 있다!

각 요소별 갯수 구하고 싶을 때는 딕셔너리를 활용하도록 하자.