[백준 BOJ] 1969번 DNA (C++/cpp)

문제 설명

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

 

 

접근 방법 - 문자열에 대한 간단한 그리디 알고리즘 문제

백준의 1969번 문제는 문자열에 대하여 비교적 해결이 쉬운 브루트포스+그리디 알고리즘 연산 문제이다.

해당 문제는, 주어진 DNA들에 대하여 각 Hamming Distance의 합이 가장 작은 DNA를 별도로 알아내고 그에 대한 Hamming Distance 합의 최솟값을 출력해야 하는 문제이다.

이때 Hamming Distance란 길이가 같은 두 DNA에 대하여 각 위치에 대하여 배정된 문자가 다른 위치의 개수를 뜻한다.

예를 들어,
TATGATAC
TAAGCTAC
라는 2개의 데이터를 보자.

이때, 배정된 문자가 다른 위치의 개수가 총 2개인 점을 확인할 수 있다.
따라서 이 2개의 DNA에 대한 Hamming Distance 값은 2라고 볼 수 있겠다.

 

근데 사실 필자도 풀이 자체는 쉽게 했는데 문제 이해를 계속 못 해서 삽질했던 문제였다...

그래서 자세한 해설은 예제 입력 1)에 대한 풀이로 설명을 이어가 보려 한다.

예제 입력 1)에 대해서 어떻게 예제 출력 1)이 될 수 있었는지를 아래에 풀어서 적어보겠다.

예제 입력 1) 에서 제시된 5개의 DNA 데이터다.
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

(1) 첫번째 위치의 문자는 각각 T, T, A, T, T이다. 이때 가장 많이 나타난 것은 T.
(2) 두번째 위치의 문자는 각각 A, A, A, G, A이다. 이때 가장 많이 나타난 것은 A.
(3) 세번째 위치의 문자는 각각 T, A, A, A, A이다. 이때 가장 많이 나타난 것은 A.
(4) 네번째 위치의 문자는 각각 G, G, G, G, G이다. 이때 가장 많이 나타난 것은 G.
(5) 다섯번째 위치의 문자는 각각 A, C, A, A, A이다. 이때 가장 많이 나타난 것은 A.
(6) 여섯번째 위치의 문자는 각각 T, T, T, T, T이다. 이때 가장 많이 나타난 것은 T.
(7) 일곱번째 위치의 문자는 각각 A, A, C, A, G이다. 이때 가장 많이 나타난 것은 A.
(8) 여덟번째 위치의 문자는 각각 C, C, C, C, T이다. 이때 가장 많이 나타난 것은 C.

위 5개의 DNA에 대하여, Hamming Distance값이 최소인 DNA를 알아내야 하기 때문에 각 자리에 대하여 가장 많이 나타난 알파벳을 순차적으로 조합하는 방법을 통해 찾아보았다.
따라서 위 8개 자리에 있어 가장 많이 나온 알파벳들을 순서대로 조합하면 "TAAGATAC".
따라서 첫번째 정답은 "TAAGATAC"라고 볼 수 있겠다.

두 번째 정답은 첫 번째 정답인 "TAAGATAC"와 입력으로 주어졌던 5개 DNA의 각 Hamming Distance 값의 총합을 구하면 된다.
필자 편의상, "TAAGATAC"와 각 자릿수 별로 다르게 배정된 알파벳의 개수를 세어보면, 1+1+1+0+1+0+2+1=7.
따라서 두번째 정답은 7이라고 볼 수 있겠다.

 

필자는 위 풀이 방식을 기반으로 아래의 코드를 작성하여서 정답을 찾을 수 있었다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 위의 설명과 아래의 코드 설명을 함께 참고하면 된다.

필자는 아래처러 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) DNA의 개수(n)와 모든 DNA의 길이(m)를 입력받는다.

 

2) DNA를 문자열 형태로 입력받아서 저장할 벡터 dna를 선언해 둔다.

그리고 각 위치에 대하여, A~Z 알파벳의 빈도수를 측정할 배열 alpha를 모두 0으로 초기화하여 선언해 둔다.

(행(51)은 dna의 각 위치를 뜻하고, 열(26)은 A~Z의 각 빈도수를 뜻한다.)

 

3) n의 크기만큼, 반복문을 실행하여 아래의 연산을 취한다.

- DNA 정보(st)를 순차적으로 입력받고, 그대로 벡터 dna에 저장하도록 한다.

- st의 각 자리와 각 알파벳에 대하여 alpha의 적절한 위치에 1을 더하도록 한다.

(예를 들어, st[1]의 문자 값이 'A'라면 alpha[1][0] 위치에 1을 더하여 빈도수를 측정하도록 한다.)

 

4) Hamming Distance값이 최소인 DNA를 별도로 저장할 p를 선언한다.

이때 문자열 p에 문자를 하나씩 더해나갈 예정이니 "" 또는 null로 초기화하도록 한다.

 

5) DNA의 길이인 m의 크기만큼, 반복문을 실행하여 아래의 연산을 취한다.

- 해당되는 위치에서 가장 많이 나타난 알파벳을 저장해 둘 문자 a를 선언한다.

- 특정 알파벳의 최대 빈도수를 저장할 변수 max를 0으로 초기화하여 선언한다.

- alpha의 현재 위치에 대해서 각 알파벳의 빈도수를 탐색한다.

이때, 가장 많이 나타난 알파벳이 탐색되었다면 max의 값을 alpha의 현재 값으로 갱신하고 a도 해당 알파벳으로 저장한다.

- 문자 a의 선정이 완료되었다면, 해당 문자를 p에 포함시킨다.

 

6) 5)를 통하여 첫 번째 정답을 구하였다면, 이에 대한 Hamming Distance를 구해야 한다.

- Hamming Distance의 총합을 저장할 변수 count를 0으로 초기화하여 선언한다.

- n개 DNA의 m개의 자리에 대하여, p와 다르게 배정된 알파벳을 발견한다면 count에 1씩 더하도록 한다.

 

7) 위 연산을 모두 완료하였다면, 최종적으로 저장된 p와 count를 순차적으로 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#include <string>
#define endl '\n'
using namespace std;

// 백준 1969번 코드
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

    int n, m;
    cin >> n >> m;
    cin.ignore();

    vector<string> dna;
    int alpha[51][26] = { 0 };
    for (int i = 0; i < n; i++) {
        string st;
        cin >> st;
        dna.push_back(st);

        for (int j = 0; j < m; j++) {
            alpha[j][st[j] - 'A']++;
        }
    }

    string p = "";
    for (int i = 0; i < m; i++) {
        char a;
        int max = 0;
        for (int j = 0; j < 26; j++) {
            if (max < alpha[i][j]) {
                max = alpha[i][j];
                a = j + 'A';
            }
        }
        p += a;
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (dna[i][j] != p[j]) {
                count++;
            }
        }
    }
    cout << p << endl << count << endl;
}

 

제출 결과

(2024.04.28 백준 1969번 문제 제출 결과)

문해력은 어떻게 극복을 못 하는건가;;