DNA

1969번: DNA

🤔생각해보기

처음에는 문제가 무슨 뜻인지 이해가 잘 되지 않았어서 한참을 들여다본거 같다.

새로운 DNA 배열을 만들고 싶은데 다른 DNA들과 비교했을 때 각 위치의 문자가 다른 것의 합계가 가장 작은 새로운 DNA 배열이 만들고 싶다라는 말이 뭐가 이렇게 길고 복잡한건지...

1. 염기서열을 쭉 늘어놓았을 때 각각의 위치에서 가장 많은 문자는 무엇인지 세는 것으로 시작한다. 위치마다 가장 많은 문자를 골라내서 새로운 DNA 를 구성하게 하면 자연스럽게 다른 부분이 가장 적은 DNA 가 된다.
2. 만약 개수가 같은 문자가 있다면 사전순으로 선택한다.
3. 2번 과정을 거치고 나면 새로운 DNA 가 만들어져 있다. 이 DNA를 roop를 돌며 다른 부분을 찾고 개수를 구한다.

Code

from collections import Counter

N, M = map(int, input().split())
dna = [input() for _ in range(N)]

s = zip(*dna)
result = []

# 1, 2번 과정
for i in s:
    common = sorted(Counter(i).most_common(), key=lambda x: (-x[1], x[0]))
    result.append(common[0][0])

# 3번 과정
count = 0
for i in dna:
    count += len(list(filter(lambda x: x[0] != x[1], zip(i, result))))

print(''.join(result))
print(count)

 

• Counter.most_common() 은 해당 배열의 요소를 모두 카운팅한 뒤에 많은 순서로 정렬하기 때문에 이 문제와 잘 어울리는 선택지 중 하나다. 하지만 정렬 조건이 하나 더 있기 때문에 lambda 를 사용해서 해결했다.
• zip() 을 적극적으로 활용하면 편리하게 해결할 수 있다.