[Python] 그리디- 1969. DNA(실4)

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

1969번: DNA

 

>>문제 포인트

- distance가 작기 위해서는 각 열별로 가장 많이 나온 분자를 가져야 함

- 예를 들어 다음과 같이 DNA가 주어졌다면 세로로 최빈값을 판단한다.

 

T  A  T  G  A  T  A  C

T  A  A  G  C  T  A  C

A  A  A  G  A  T  C  C

T  G  A  G  A  T  A  C

T  A  A  G  A  T  G  T

 

1열은 : T T A T T => T(4) / A(1) => 최빈값이 T / distance는 +1

2열은 : A A A G A => A(4) / G(1) => 최빈값이 A / distance는 +1

3열은 : T A A A A => A(4) / T(1) => 최빈값이 A / distance는 +1

.

.

.

식으로 세로로 8개의 행을 파악하면 된다.

 

- 사전식이라고 했으므로 A C G T를 순서대로 배열하고 max값 조회로 사전순부터 튀어나오게 list를 만든다.

---

>>코드

dna=['A','C','G','T']

#코드 출현 빈도
dna_num = [0]*4

#주어지는 dna들
dna_list=[]

#결과값
result=''
distance=0

n,m= map(int, input().split())

#dna_list에 염기서열 다 추가하기
for _ in range(n):
  k=input()
  dna_list.append(k)

#0~m까지 각 최빈값 검사
for i in range(m):
  
  for j in dna_list:
    if j[i]=='A':
      dna_num[0]+=1
    elif j[i]=='C':
      dna_num[1]+=1
    elif j[i]=='G':
      dna_num[2]+=1
    else:
      dna_num[3]+=1
  
  #최빈값의 index를 dna에서 찾아 더해줌      
  result+=dna[dna_num.index(max(dna_num))]
  
  # 전체 개수(n) - 최빈값이 distance가 됨
  distance+= (n-max(dna_num))
  
  #다음 열 검사를 위해 초기화
  dna_num = [0]*4

print(result)
print(distance)