[탐욕법] DNA (특정 요소의 개수 세기)

문제

TIP

1. 알파벳과 같이 어떠한 값이 나올지 이미 예측되는 경우에는 배열의 인덱스에 각각 그 값을 부여할 수 있다.

예를 들어 해당 문제의 배열 dnaCounter[4]는 A C G T 순으로 임의로 부여하였다.

이를 새로운 값이 나올때마다 객체의 새로운 인자로 추가하는 식은 문제를 어렵게 한다.

 

2. Hamming Distance의 합은 차이를 모두 더할 수도 있지만, 모든 문자열에서 같은 문자열을 빼는 것으로 쉽게 얻을 수도 있다. 꼭 합이라고 덧셈만을 고집하지 말자.

 

 3. for문과 if문이 어떤 결과를 가져올지 눈으로 확인하기 전에 머리로 이해하자

 

CODE

#include <iostream>
using namespace std;
 
int main() {
    int count, length;
    cin >> count >> length;
    char arr[1000][50]; 
    int dnaCounter[50][4]; // A C G T 순 
    char bestDNA[length];
    
    for(int i=0; i<count; i++) {
        for(int j =0; j<length; j++) {
            cin >> arr[i][j];
        }
    }
    
    for(int i=0; i<count; i++) {
        for(int j =0; j<length; j++) {
             if (arr[i][j] == 'A'){
                 dnaCounter[j][0] = dnaCounter[j][0]+1 ;    
             } else if(arr[i][j] == 'C') {
                 dnaCounter[j][1] = dnaCounter[j][1]+1 ;    
             } else if(arr[i][j] == 'G')  {
                 dnaCounter[j][2] = dnaCounter[j][2]+1 ;
             } else if(arr[i][j] == 'T'){
                 dnaCounter[j][3] = dnaCounter[j][3]+1 ;
             } 
        }
    }
    
    int maxiumAppear = 0;
    int maxiumIndex;
    int differentNumber = count * length;
    
 
    char appearDNA;
    for(int i=0; i<length; i++) {
        maxiumAppear = 0;    
        for(int j =3; j>=0; j--) {
            if(maxiumAppear <= dnaCounter[i][j]) {
                maxiumAppear = dnaCounter[i][j];
                if(j == 3) appearDNA = 'T';
                if(j == 2) appearDNA = 'G';
                if(j == 1) appearDNA = 'C';
                if(j == 0) appearDNA = 'A';
                maxiumIndex = j;
            }      
        }
        differentNumber -= dnaCounter[i][maxiumIndex];
        bestDNA[i] = appearDNA;
    }
    
    for(int i =0; i<length; i++) {
        cout << bestDNA[i];
    }
    
    cout << "\n" << differentNumber;
    
    
    return 0;
}