[백준] 1969번_DNA C++

29 Jan 2023 in Study on Coding Test

완전탐색(브루트포스)을 이용해서 푸는 문제

정답제출코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 각 자리 순서대로 A T G C의 개수
int NewCleo[4] = {0, 0, 0, 0};

vector<string> DNAs;
int N, M;

int main()
{
    cin >> N >> M;

    for (int i = 0; i < N; ++i)
    {
        string s;
        cin >> s;
        DNAs.push_back(s);
    }

    string HD_min;
    int max, min_count = 0;

    for (int i = 0; i < M; ++i)
    {
        // 각 자리마다 가장 많은 뉴클레오타이드를 구함.
        for (int j = 0; j < N; ++j)
        {
            if (DNAs[j][i] == 'A')
                NewCleo[0]++;
            else if (DNAs[j][i] == 'T')
                NewCleo[1]++;
            else if (DNAs[j][i] == 'G')
                NewCleo[2]++;
            else if (DNAs[j][i] == 'C')
                NewCleo[3]++;
        }

        if (NewCleo[0] >= NewCleo[1] && NewCleo[0] >= NewCleo[2] && NewCleo[0] >= NewCleo[3])
        {
            HD_min.push_back('A');
            max = NewCleo[0];
        }

        else if (NewCleo[1] > NewCleo[0] && NewCleo[1] > NewCleo[2] && NewCleo[1] > NewCleo[3])
        {
            HD_min.push_back('T');
            max = NewCleo[1];
        }
        else if (NewCleo[2] > NewCleo[0] && NewCleo[2] >= NewCleo[1] && NewCleo[2] > NewCleo[3])
        {
            HD_min.push_back('G');
            max = NewCleo[2];
        }
        else if (NewCleo[3] > NewCleo[0] && NewCleo[3] >= NewCleo[1] && NewCleo[3] >= NewCleo[2])
        {
            HD_min.push_back('C');
            max = NewCleo[3];
        }

        min_count += N - max;

        // 초기화
        NewCleo[0] = 0;
        NewCleo[1] = 0;
        NewCleo[2] = 0;
        NewCleo[3] = 0;
    }

    cout << HD_min << '\n';
    cout << min_count;

    return 0;
}

따지고보면 각 열마다 가장 많은 알파벳을 순서대로 넣어주면 DNA는 완성된다.

그리고 내 발목을 잡았던 문제는 같은 개수의 문자가 있을 때였다.

예를 들어, 6개의 DNA가 있는데 각 DNA의 1열의 구성이 T,T,T,A,A,A 일때이다.

이러면 T가 3개, A가 3개 있어서 어떤 알파벳을 넣어야할지 애매해진다.

여기서 문제에서 사전순으로 출력하라고 조건을 주어졌으니 나는 부등호를 이용했다.

        if (NewCleo[0] >= NewCleo[1] && NewCleo[0] >= NewCleo[2] && NewCleo[0] >= NewCleo[3])
        {
            HD_min.push_back('A');
            max = NewCleo[0];
        }

        else if (NewCleo[1] > NewCleo[0] && NewCleo[1] > NewCleo[2] && NewCleo[1] > NewCleo[3])
        {
            HD_min.push_back('T');
            max = NewCleo[1];
        }
        else if (NewCleo[2] > NewCleo[0] && NewCleo[2] >= NewCleo[1] && NewCleo[2] > NewCleo[3])
        {
            HD_min.push_back('G');
            max = NewCleo[2];
        }
        else if (NewCleo[3] > NewCleo[0] && NewCleo[3] >= NewCleo[1] && NewCleo[3] >= NewCleo[2])
        {
            HD_min.push_back('C');
            max = NewCleo[3];
        }

이쪽 코드에서 원래는 부등호들이 전부다 >= 모양이었다.

하지만 같은 개수가 나와야 한다면 사전 순으로 출력해야하기 때문에 위와 같이 부등호를 조절했다.

그렇게 해서 정답을 얻을 수 있었다.