[백준] 1969 DNA - 완전탐색 + 구현 JAVA

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

1969번: DNA

 

문제풀이

완전탐색 문제였습니다.

처음에 문제이해를 잘못하여 아예 잘못풀고 다시 풀었습니다.

문제조건에

• N개의 길이 M인 DNA s1, s2, ..., sn가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 s1의 Hamming Distance + s와 s2의 Hamming Distance + s와 s3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

처음에 문제이해를 이상하게 했습니다.

5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

이 입력값이 있을때

TATGATAC 와 나머지 4가지를 비교

TAAGCTAC 와 나머지 4가지를 비교...

 

이렇게 하면서 가장 hamming distance 의 합이 작은것을 구했습니다.

 

그러나 나중에 다시보니,

위의 값들이 있을떄 새로운 DNA 를 구하는 것입니다.

저는 첫번쨰 코드는 기존의 DNA중에서 가장 DNA가 같은것을 고르는줄 알고 코딩하였습니다.

코드

오류코드 ( 기존 DNA에서 hamming DIstnace가 가장 작은 것을 구한 코드 )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int N, M;
	public static String[] DNA;
	public static int ResultDNAIndex = 0;
	public static int Result = Integer.MAX_VALUE;
	public static ArrayList<String> arr = new ArrayList<String>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	DNA = new String[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		DNA[i] = st.nextToken();
    	}
    	
    	
    	simulate();
    	Collections.sort(arr);
    	System.out.println(arr.get(0));
    	System.out.println(Result);
    		  
	}
    
	//
    
    public static void simulate() {
    	int index = 0;
    	int hammingDistance = 0;
    	while(index < N) {
    		System.out.println("--------------------------");
    		System.out.println("INDEX:"+index+" "+DNA[index]);
    		System.out.println();
    		hammingDistance = 0;
    		
    		String standard = DNA[index];
        	for(int i=0;i<N;i++) {
        		if(index == i) continue;
        		String compare = DNA[i];
        		for(int j=0;j<M;j++) {
        			char standardChar = standard.charAt(j);
            		char compareChar = compare.charAt(j);
            		if(standardChar != compareChar) {
            			
            			hammingDistance += 1;
            			System.out.println("STANDARDCHAR, CompareCHAR "+standardChar +" "+compareChar+" "+hammingDistance);
            		}
        		}
        		
        	}
        	
        	
        	if(Result > hammingDistance) {
        		Result = hammingDistance;
        		ResultDNAIndex = index;
        		arr.add(DNA[index]);
        	}
        	
        	index +=1;
    	}
    	

    	
    }
    
    
}

 

새로운 DNA를 구한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int N, M;
	public static int[] NEWCLEOTD; //(A, C, G, T)   사전순이기에 A C G T로 선언해줍니다.
	public static String[] DNA;
	public static int Result = Integer.MAX_VALUE;
	public static int hammingDistance = 0;
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	DNA = new String[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		DNA[i] = st.nextToken();
    	}
    	
    	simulate();
    	System.out.println(sb.toString());
    	System.out.println(hammingDistance);
    		  
	}
    
    public static void simulate() {
    	
    	for(int i=0;i<M;i++) {
    		NEWCLEOTD = new int[4];
    		for(int j=0;j<N;j++) {
    			
    			if(DNA[j].charAt(i) == 'A') {  //A라면 NEWCLEOTD에 count해줍니다.
    				NEWCLEOTD[0] += 1;
    			}else if(DNA[j].charAt(i) == 'C') { // NEWCLEOTD에 count해줍니다.
    				NEWCLEOTD[1] += 1;
    			}else if(DNA[j].charAt(i) == 'G') { //  NEWCLEOTD에 count해줍니다.
    				NEWCLEOTD[2] += 1;
    			}else if(DNA[j].charAt(i) == 'T') { //  NEWCLEOTD에 count해줍니다.
    				NEWCLEOTD[3] += 1;
    			}
    			
    		}
    		
    		int maxIndex = 0;
    		int maxCount = NEWCLEOTD[0];
    		for(int j=0;j<NEWCLEOTD.length;j++) { //가장 많이 나온 DNA를 구합니다.
    			if(maxCount < NEWCLEOTD[j]) {  
    				maxIndex = j;
    				maxCount = NEWCLEOTD[j];
    			}
    		}
    		
    		for(int j=0;j<4;j++) {  //hammingDistance를 구하기 위해 maxIndex와 다른 값들 중에 다른 값들의 합이 총 다른값의 합입니다.
    			if( j != maxIndex) {
    				hammingDistance += NEWCLEOTD[j];
    			}
    		}
    		
    		if(maxIndex == 0) { //maxIndex가 0 이면 'A'를 더해줍니다.
    			sb.append('A');	
    		}else if(maxIndex == 1) {
    			sb.append('C');	
    		}else if(maxIndex == 2) {
    			sb.append('G');	
    		}else if(maxIndex == 3) {
    			sb.append('T');	
    		}
    		
    	}
    	
    }
}