[백준][BOJ 1969] - DNA

문제

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

1969번: DNA

 

 

문제 접근

• 주어진 DNA입력들에 대해 Hamming Distance가 최소가 되는 DNA를 우리가 만들어야 한다.
• Hamming Distance의 경우 우리가 만든 DNA를 $s$라고 할 때 이 $s$의 각 부분과 주어진 DNA들의 각 부분을 비교해 다른 글자의 개수로 정의된다.
• 따라서 Hamming Distance를 최소화 시키기 위해서는 주어진 DNA의 각 부분(또는 자리)에 대해 어떤 글자를 가지고 있는지를 확인해서 제일 많은 글자를 사용해야 할 것이다.
• 예를 들어서 다음과 같은 입력을 보자

5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

• 첫 번째 글자들을 보도록 하자. 현재 첫 번째 글자는 T 또는 A로 분류할 수 있다. 이때 Hamming Distance를 최소화 시키기 위해서는 당연하게도 첫 글자를 T로 하는 것이 좋을 것이다.
  • T를 첫 번째 글자로 선정한다면 우리가 만든 DNA의 첫 번째 글자에 대한 Hamming Distance의 합은 1이다. 왜냐하면 3번째 DNA에서만 다른 글자(A)가 존재하기 때문이다.
  • 반면 A를 첫 번째 글자로 선정한다면 우리가 만든 DNA의 첫 번째 글자에 대한 Hamming Distance의 합은 4가 된다. 왜냐하면 1, 2, 4, 5번째 DNA가 모두 다른 글자(T)이기 때문이다.
• 따라서 다음과 같은 순서를 통해 Hamming Distance가 최소화되는 DNA를 만들 수 있다.
  • 각 자릿수에 대해 글자들을 카운트한다.
  • 이후 가장 많이 카운트된 글자를 선택한다. 만약 모두 동일하거나, 가장 많이 카운트된 글자들이 복수로 존재한다면, 사전순으로 빠른 글자를 선택한다.
  • 이후 가장 많이 카운트된 글자를 선택했을 때의 Hamming Distance를 계산한다.
• Hamming Distance의 경우 다른 글자의 개수로 정의된다. 이때 우리는 각 자릿수에 대해 글자들을 카운트한 데이터가 있으므로 이 데이터를 활용하여 Hamming Distance를 계산할 수 있다.
  • Hamming Distance는 다음과 같이 계산이 가능하다. 이때 $N$은 주어진 DNA의 개수이고, $count$는 카운트된 데이터의 배열이다.
  • $D = N - \max(count)$

 

 

 

정답 코드

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

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    String[] data = new String[N];

    char[] dnaElement = {'A', 'C', 'G', 'T'};
    int hammingDistance = 0;

    for (int i = 0; i < N; i++) {
      data[i] = br.readLine();
    }

    StringBuilder sb = new StringBuilder();

    for (int j = 0; j < M; j++) {
      int[] count = new int[4];
      int maxCount = -1;
      int maxCountIdx = -1;

      for (int i = 0; i < N; i++) {
        char element = data[i].charAt(j);

        if (element == 'A') {
          count[0]++;
        } else if (element == 'C') {
          count[1]++;
        } else if (element == 'G') {
          count[2]++;
        } else if (element == 'T') {
          count[3]++;
        }
      }

      for (int i = 0; i < 4; i++) {
        if (count[i] > maxCount) {
          maxCount = count[i];
          maxCountIdx = i;
        }
      }

      sb.append(dnaElement[maxCountIdx]);
      hammingDistance += N - count[maxCountIdx];
    }

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

  }
}