[백준] 1969번 - DNA

문제 >

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자를 따서 표현한다. 만약에 Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-Cytosine-Cytosine-Guanine-Adenine-Thymine로 이루어진 DNA가 있다고 하면, “TAACTGCCGAT”로 표현할 수 있다. 그리고 Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클오티드 문자가 다른 것의 개수이다. 만약에 “AGCAT"와 ”GGAAT"는 첫 번째 글자와 세 번째 글자가 다르므로 Hamming Distance는 2이다.

우리가 할 일은 다음과 같다. n개의 길이가 같은 DNA가 주어져 있을 때(이 DNA를 a1a2a3a4...이라고 하자) Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 a1의 Hamming Distance + s와 a2의 Hamming Distance + s와 a3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

 

입력 >

첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

출력 >

첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

 

해결방법 > 

그리디 알고리즘으로 해결

 

각 문자열의 n 번째 문자를 순회하면서 제일 많이 카운트 된 문자를 찾는다

 

[C++]

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n, len;
    vector <string> v;
    vector <char> c;
    int comp = 0;

    cin >> n >> len;

    for(int i = 0; i < n; i++){
        string tmp;
        cin >> tmp;
        v.push_back(tmp);
    }

    for(int i = 0; i < len; i++){
        int arr[4] = {0, 0, 0, 0};
        for(int j = 0; j < n; j++){
            switch (v[j][i]){
            case 'A':
                arr[0]++;
                break;
            case 'C':
                arr[1]++;
                break;
            case 'G':
                arr[2]++;
                break;
            case 'T':
                arr[3]++;
                break;
            }
        }
        int max = 0;
        int idx;
        for(int j = 0; j < 4; j++){
            if(arr[j] > max){
                max = arr[j];
                idx = j;
            }
        }

        switch (idx){
        case 0:
            c.push_back('A');
            break;
        case 1:
            c.push_back('C');
            break;
        case 2:
            c.push_back('G');
            break;
        case 3:
            c.push_back('T');
            break;
        }

    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < len; j++){
            if(c[j] != v[i][j])
                comp++;
        }
    }
    for(int i = 0; i < c.size(); i++){
        cout << c[i];
    }
    cout<< "\n" << comp;
}

 

[JAVA]

import java.util.*;

public class BOJ_1969{
	static class Node implements Comparable<Node>{
		char c;
		int cnt;
		
		Node(char c, int cnt){
			this.c = c;
			this.cnt = cnt;
		}
		
		@Override
		public int compareTo(Node n) {
			if(this.cnt == n.cnt) {
				if(this.c < n.c)
					return -1;
				else
					return 1;
			}
			else if(this.cnt > n.cnt)
				return -1;
			else
				return 1;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		char[][] input = new char[x][y];
		char[] output = new char[y];
		int distance = 0;
		
		for(int i = 0; i < x; i++) {
			String s = sc.next();
			for(int j = 0; j < y; j ++) {
				input[i][j] = s.charAt(j);
			}
		}
		
		for(int i = 0; i < y; i++) {
			ArrayList <Node> list = new ArrayList();
			for(int j = 0; j < x; j++) {
				boolean flag = false;
				
				for(int k = 0; k < list.size(); k++) {
					if(list.get(k).c == input[j][i]) {
						list.get(k).cnt++;
						flag = true;
					}
				}
				if(flag == false)
					list.add(new Node(input[j][i], 1));
			}
			Collections.sort(list);
			
			output[i] = list.get(0).c;
		}
		
		for(int i = 0; i < x; i++) {
			for(int j = 0; j < y; j++) {
				if(i == 0)
					System.out.print(output[j]);
				if(output[j] != input[i][j])
					distance++;
			}
		}
		System.out.println("\n" + distance);
	}
}

 

문제링크 >

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

1969번: DNA