(Baekjoon) GreedyAlgorithm - (21) DNA

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

1969번: DNA

 

대충 생각해보았을때 전부다 분석하는데 걸리는 시간은 어림잡아 O(n^2) 로 예상된다.

for(){ 
	for(){ 

	} 
} 

 

가장 차이가 적다는말은 가장 유사성이 높다는말과 같다.

그러므로 가장 많이 쓰인 뉴클레오티드를 사용하면 될것같다.

 

input : N(개수),M(길이)

output : 유사성높은 DNA, 나머지와의 차이

 

Adenine, Thymine, Guanine, Cytosine (A, T, G, C)의 개수를 파악할 배열

int DNA[M][4]; // ATGC 개수파악

char dna[N][M]; // dna 문자열 저장

 

DNA의 개수를 파악후 가장 많은것을 출력한다.

이때 비교할때 문자열 순서대로 와야하기 때문에 A,C,G,T 순서대로 비교를 한다.

 

---------------------------------------------------------------

 

문제를 잘못파악했다. 문자열 s는 기존에 주어진 DNA집합에 속한 원소가 아닌 새로운 원소 s라고 가정해야된다.

(문제를 잘못읽었다. 다음부턴 꼼꼼히 읽어야겠다.)

 

package GreedyAlgorithm;

import java.util.Scanner;

public class _1969 {

    static int DNA[][];
    static int N, M;
    static char dna[][];
    static String C;    
    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        DNA = new int[M][4];
        dna = new char[N][M];
        
        for (int j = 0; j < N; j++) {
            C = sc.next();
            for (int i = 0; i < M; i++){
                dna[j][i] = C.charAt(i);
                if (C.charAt(i)=='A')
                    DNA[i][0]++;
                else if (C.charAt(i)=='C')
                    DNA[i][1]++;
                else if (C.charAt(i)=='G')
                    DNA[i][2]++;
                else
                    DNA[i][3]++;
            }
        }

        char dap[] = new char[M];

        for (int i = 0; i < M; i++) {
            if (DNA[i][0] >= DNA[i][1] && DNA[i][0] >= DNA[i][2] && DNA[i][0] >= DNA[i][3]) 
                dap[i] = 'A';            
            else if (DNA[i][1] >= DNA[i][0] && DNA[i][1] >= DNA[i][2] && DNA[i][1] >= DNA[i][3])
                dap[i] = 'C';
            else if (DNA[i][2] >= DNA[i][3] && DNA[i][2] >= DNA[i][1] && DNA[i][2] >= DNA[i][0])
                dap[i] = 'G';
            else
                dap[i] = 'T';
        }

       for (int i = 0; i < M; i++) {
           System.out.print(dap[i]);
       }
       int n=0;
       for (int i = 0; i < N ; i++) {
           for (int j = 0; j < M ; j++) {
               if(dna[i][j] != dap[j]) n++;
           }
       }
       System.out.println("\n"+n);


        sc.close();

    }
}

 

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study