백준 1969번 DNA

문제 링크입니다: https://www.acmicpc.net/problem/1969

그리디(Greedy) 알고리즘으로 분류되어있지만 오히려 브루트 포스(Brute Force) 알고리즘에 가까운 문제였습니다.

처음에 문제에서 요구하는 바를 이해하지 못해서 어렵게 느껴졌는데 이해하고 나니까 엄청 쉬운 문제였습니다.

결국 문제에서 요구하는 것은 각 인덱스에서 제일 많이 쓰인 알파벳을 구하고(사전순) 각각의 알파벳의 개수에 대해 Hamming Distance의 누적합을 구하는 것이였습니다.

알고리즘은 아래와 같습니다.

1. Cache 배열에 각 인덱스당 A, C, G, T가 몇 개 사용되었는지 기록합니다.

->A, C, G, T 순으로 저장하는 이유는 사전순에서 제일 빠른 단어를 출력하기 위해서입니다.

2. 반복문을 돌리면서 제일 많이 쓰인 알파벳을 출력하고 Hamming Distance를 계산합니다.

3. 마지막에 Hamming Distance의 누적합을 출력해주면 됩니다.

#include <iostream>

#include <string>

using namespace std;

 

const int MAX = 50;

 

int N, M;

int cache[MAX][4]; //i번째, {A, C, G, T}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> M;

 

        for (int i = 0; i < N; i++)

        {

                 string temp;

                 cin >> temp;

 

                 //각 idx에 어떤 알파벳이 몇번 쓰였는지 계산

                 for (int j = 0; j < temp.length(); j++)

                         switch (temp[j])

                         {

                         case 'A':

                                 cache[j][0]++;

                                 break;

                         case 'C':

                                 cache[j][1]++;

                                 break;

                         case 'G':

                                 cache[j][2]++;

                                 break;

                         case 'T':

                                 cache[j][3]++;

                                 break;

                         }

        }

       

        //Hamming Distance 기록

        int result = 0;

        string DNA = "";

        //각 idx에 가장 많이 사용된 문자 사용

        for (int i = 0; i < M; i++)

        {

                 int idx=0, cnt = 0;

                 for(int j=0; j<4; j++)

                         if (cache[i][j] > cnt)

                         {

                                 idx = j;

                                 cnt = cache[i][j];

                         }

 

                 result += (N - cnt);

                 //사전순

                 switch (idx)

                 {

                 case 0:

                         DNA += 'A';

                         break;

                 case 1:

                         DNA += 'C';

                         break;

                 case 2:

                         DNA += 'G';

                         break;

                 case 3:

                         DNA += 'T';

                         break;

                 }

        }

        cout << DNA << "\n";

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~