[백준] 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가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

 

사실 이 문제는 그리디가 아니다. 하지만 그리디라고 해도 상관없을지도 모른다.

이 문제는... 부루트 포스 문제입니다.

 

이 문제를 쉽게 풀기 위해서는  예제 코드를 잘 보면 쉽게 해결이 가능하다.

5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

이건데...

보면 어떻게 하면 최소가 나올까 생각해야 한다.

 

세로로 알파벳을 보았다. 그리고 그중 많은것만 따로 분류 해보았다.

놀랍게도 T A A G T A C 가 나온다.

흠.... 이렇게 하면 모든 경우의 수에서 최소가 나온다.

 

첫번째 T A T G A T A C 같은 경우 1이 나온다. 이런식으로

구하면 총 갯수는 7개가 나왔다.

 

근데 이걸 어떻게 풀까?

 

import java.io.IOException;
import java.util.Scanner;

public class Main {
	static char[] a= {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S',
			         'T','U','V','W','X','Y','Z'};
	
	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);

		int n, m;
		n = sc.nextInt();
		m = sc.nextInt();

		String[] DNAs = new String[n];

		for (int i = 0; i < n; i++) {
			DNAs[i] = sc.next();
		}

		String ans = "";
		int count = 0;
		for (int i = 0; i < m; i++) {
			int alpa[] = new int[26];
			int max = -1;
			int total = 0;
			for (int j = 0; j < n; j++) {
				alpa[DNAs[j].charAt(i) - 'A']++;
			}

			int index = -1;
			for (int k = 0; k < 26; k++) {
				total+= alpa[k];
				if (max < alpa[k]) {
					max = alpa[k];
					index = k;
				}
			}
			
			count += (total - max);
			ans += a[index];
			
		}
		
		System.out.println(ans);
		System.out.println(count);
	}
}

나는 이런식으로 구현하였다.

세로니까 m부터 하고... alpa라는 배열을 만든뒤 그곳에 집어 넣었다.

이렇게 만들면 세로에 알파벳이 얼마나 존재하는지 셀수 있다.

 

여기서 중요한건 n과 m은 자리를 절대 바꾸면 안된다. 그러면

 

이제 alpa라는 배열에 값들이 들어오겠지...

 

그리고 반복문을 돌려서 최댓값을 찾았다.

근데 중요한게 Math.max()를 사용하면 안된다. 특히 위 소스에서는 절대로 사용하면 안된다.

왜냐하면 index도 값을 구해야하는데 이러면 값을 구할 수 없기 때문이다.

 

index를 구해야하는 이유는 DNA값을 구해야하기 때문이다.

 

나는 total 에서 max를 뺏다. 왜 max를 뺀 이유는

총 갯수에서 가장 많은 수를 빼면 최소 값을 구할 수 있기 때문이다.

이럴게 구하고 각각 count 와 ans에 값을 저장한뒤 출력하였다.

 

사실 설명하면서도 조금 어려운건 사실이다. 이 문제는 설명이 더 어려운 것 같다.

 

나는 사전순을 고려하지 않았다. 그 이유는 if 문의 특성때문인데

알파벳은 A,B,C순서 대로 들어오기 때문에 A가 들어오고 나머지와 갯수가 같으면 값을 구하지 않기 때문이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String countAndLength = br.readLine();
        String[] countAndLengthArray = countAndLength.split(" ");

        int dnaAmonut = Integer.parseInt(countAndLengthArray[0]);
        String[] dnaArray = setDNAList(br, dnaAmonut);

        List<String[]> list = getHammingDNAList(dnaArray, Integer.parseInt(countAndLengthArray[1]));

        StringBuilder sb = new StringBuilder();
        int answer = 0;
        for (String[] array : list) {
            sb.append(array[0]);
            answer += (dnaAmonut - Integer.parseInt(array[1]));
        }

        System.out.println(sb.toString());
        System.out.println(answer);

    }

    private static String[] setDNAList(BufferedReader br, int dnaAmount) throws IOException {
        String[] dnaArray = new String[dnaAmount];
        for (int i = 0; i < dnaAmount; i++) {
            dnaArray[i] = br.readLine();
        }

        return dnaArray;
    }

    private static List<String[]> getHammingDNAList(String[] dnaArray, int dnaLength) {
        List<String[]> list = new ArrayList<String[]>();
        for (int i = 0; i < dnaLength; i++) {

            Map<Character, Integer> map = new HashMap<Character, Integer>();
            for (int j = 0; j < dnaArray.length; j++) {
                int count = 1;
                char dnaElement = dnaArray[j].charAt(i);
                if (map.containsKey(dnaElement)) {
                    count += map.get(dnaElement);
                }

                map.put(dnaElement, count);
            }

            String[] dnaFrontAndCount = new String[2];
            int max = 0;
            for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                Character key = entry.getKey();
                Integer count = entry.getValue();

                if (count > max) {
                    max = count;
                    dnaFrontAndCount[0] = String.valueOf(key);
                    dnaFrontAndCount[1] = String.valueOf(max);
                } else if (count == max) {
                    char charKey = dnaFrontAndCount[0].charAt(0) > (char) key ? key : dnaFrontAndCount[0].charAt(0);

                    dnaFrontAndCount[0] = String.valueOf(charKey);
                    dnaFrontAndCount[1] = String.valueOf(max);
                }
            }

            list.add(dnaFrontAndCount);
        }

        return list;
    }
}

 흠 내 코드가 더 괜찮은 것 같은데...

짧아서 그런가...