[그리디 알고리즘] ▲ 1969번 - DNA

[백준] 1969번 - DNA

(풀이1) zip()함수로 2차원 리스트 뒤집고 Counter로 빈도수 세기

1) 문제 해결 아이디어

아이디어는 쉽게 떠올렸다.

HD란 길이가 같은 두 DNA 각 위치의 문자가 다른 것의 개수이다.

예를들어, AGCAT와 GGAAT의 HD는 2이다. (첫번째, 3번째가 다름)

 

n개의 길이 m인 DNA가 주어졌을 때, HD의 합이 최소가 되게하려면 HD값 자체가 최소가 되어야 한다.

주어진 DNA들의 각 자리 문자들 중 가장 빈도수가 높은 것을 선택해야 HD의 값이 가장 최소가 된다.

 

열 단위로 검사하려면 2차원 리스트(dna)의 행과 열을 바꾸는 것이 코드를 짜기에 편하다.

2중 for문으로 row와 column을 뒤집을 수도 있으나 여기서는 zip() 함수를 이용해 2차원 리스트를 뒤집는다.

또한 각 위치의 문자들 중 가장 빈도수가 높은 것과 빈도수를 세기 위해 Counter를 이용였다.

 

2) 소스코드

from collections import Counter

n, m = map(int, input().split())  # DNA 수, 문자열 길이
dna = [list(input()) for _ in range(n)]
# 2차원 리스트 행과 열 바꾸기
dna = list(map(list, zip(*dna)))

cnt = 0  # HD의 합
min_dna = ""  # HD의 합이 최소가되는 dna 
for i in range(m):
  # 가장 빈도수가 높은 문자 추출해서 dna 만들기
  counts = Counter(sorted(dna[i]))
  c = counts.most_common(1)[0][0]  # 가장 빈도수가 높은 문자
  num = counts.most_common(1)[0][1]  # 해당 문자의 빈도 수
  cnt += (n - num)  # 가장 빈도수가 높은 문자를 제외한 문자 수
  min_dna += c

print(min_dna)
print(cnt)

<2차원 리스트 뒤집기>

2차원 리스트의 행과 열을 바꾸는 방법이다.

a = [ [1, 2], [3, 4,], [5, 6] ] b = list(map(list, zip(*a)))

2차원 리스트(a) 2차원 리스트(a)의 행과 열을 뒤집어 새로운 리스트(b) 만들기

[참고] https://roeldowney.tistory.com/515

[python] 2차원 리스트 뒤집기 - zip

 

<Counter로 빈도수 세기>

from collections import Counter

# a: 3개, b: 2개, c:2개
list = ['a', 'b', 'b', 'c', 'a', 'a', 'c']
list.sort()	# 오름차순 정렬

counts = Counter(list)

counts.most_common(1)		# 가장 빈도수가 높은 [(단어, 빈도수)] 
counts.most_common(1)[0]	# 가장 빈도수가 높은 (단어, 빈도수)
counts.most_common(1)[0][0]	# 가장 빈도수가 높은 단어
counts.most_common(1)[0][1]	# 가장 빈도수가 높은 단어의 빈도수

counts.most_common(len(list))	# 가장 빈도수가 낮은 [(단어, 빈도수)]

 위 코드에서 오름차순 정렬 코드는 꼭 필요한 것은 아니다.

하지만 b, c처럼 빈도수가 같은 경우에 알파벳 순서로 결과값을 얻어야한다면

Counter를 생성하기 이전에 리스트를 오름차순 정렬해주어야 한다.

counts = Counter(리스트)	카운터 생성
counts.most_common(n)	n번째로 빈도수가 높은 [(단어, 빈도수)] 리스트로 반환
counts.most_common(n)[0]	n번째로 빈도수가 높은 (단어, 빈도수) 튜플로 반환
counts.most_common(n)[0][0]	n번째로 빈도수가 높은 단어 반환
counts.most_common(n)[0][1]	n번째로 빈도수가 높은 단어의 빈도수 반환

[참고] https://developeryuseon.tistory.com/37

[Python] collections.Counter() 이용한 빈도수 세기

 

(풀이2) for문으로 빈도수 세기

1) 문제 해결 아이디어

여기서는 입력받은 리스트(dna)를 뒤집지 않고 for문에서 리스트 인덱스를 이용해 열 기준으로 검사하고

일반 for문으로 빈도수를 세는 방법이다.

 

[참고] https://kongpowder.tistory.com/74

[백준/파이썬] 1969번: DNA (Python)

 

2) 소스코드

from collections import Counter

n, m = map(int, input().split())  # DNA 수, 문자열 길이
dna = [list(input()) for _ in range(n)]

# 4가지 문자
type = ('A', 'C', 'G', 'T')
cnt = 0  # HD의 합
min_dna = ""  # HD의 합이 최소가되는 dna 

# 리스트 열 기준 검사하기
for i in range(m):
  num = [0] * 4  # 빈도수
  # j번째 인덱스에 대한 각 행 문자 검사하기
  for j in range(n):
    for k in range(4):
      # 문자 빈도수 세기
      if(dna[j][i] == type[k]):
        num[k] += 1
        break

  # HD가 최소가 되는 DNA
  cnt += n - max(num)  # HD 값
  min_dna += type[num.index(max(num))]  # 최댓값의 인덱스에 해당하는 문자
    
print(min_dna)
print(cnt)

 

<리스트에서 최댓값과 인덱스 찾기>

max(리스트)	최댓값 반환
min(리스트)	최솟값 반환
리스트.index(max(리스트))	최댓값의 인덱스 반환
리스트.index(min(리스트))	최솟값의 인덱스 반환

 

[참고] https://jangjy.tistory.com/332

list 에서 최대값과 최대값의 index를 찾아보자