[알고리즘 문제] 백준1969 - DNA

문제는 Hamming Distance의 합이 가장 작은 DNA(문자열)을 구하는 문제이다. 여기서 Hamming Distance는 길이가 같은 두 DNA의 각 index에서 다른 문자의 개수이다. 

 

처음에, 입력으로 들어오는 DNA중에서 찾는 문제인 줄 알고 헤맸는데 그게 아니라 입력으로 받는 모든 DNA와 비교하여 Hamming Distance의 값이 최소가 되는 새로운 DNA을 구하는 문제이다.

 

아이디어는,

1. DNA를 모두 입력받고, 각 DNA의 첫번째, 두번째, ... 빈도수를 체크하고, 체크된 배열과 최대빈도수값은 getChar()에 넘겨준다

2. getChar() 에서는 최대빈도수 값을 가지는 문자를 찾고, 반환해준다.

 

 

문제를 풀고, 다른 사람들의 풀이를 봤는데 나의 코드보다 더 깔끔하게 했다는 느낌을 받았다. 나는 입력과 처리를 나누어서 했는데, 내가 본 코드에서는 두 과정을 한꺼번에 처리해서 좀 특이했다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        String[] arr = new String[N];

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

        String DNA = "";
        int max;
        for (int x = 0; x < M; x++) {
            int check[] = new int[123];
            max = 0;
            for (int y = 0; y < N; y++) {
                char c = arr[y].charAt(x);
                check[c]++;
                if (check[c] > max) {
                    max = check[c];
                }
            }
            DNA += getChar(check, max);
        }
        int sum = 0;

        for (int w = 0; w < N; w++) {
            String s = arr[w];
            for (int f = 0; f < s.length(); f++) {
                if (s.charAt(f) != DNA.charAt(f)) {
                    sum++;
                }
            }
        }

        System.out.println(DNA);
        System.out.println(sum);
    }

    static String getChar(int[] arr, int max) {
        boolean isFind = false;
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == max) {
                list.add(i);
            }
        }
        Collections.sort(list);
        return String.valueOf((char) (int) list.get(0));
    }
}