1969번: DNA

문제

길이가 같은 N개의 DNA 문자열이 주어집니다. DNA는 'A', 'C', 'G', 'T'의 네 가지 뉴클레오티드로만 구성되어 있습니다. 이 N개의 DNA와 해밍 거리(Hamming Distance, 길이가 같은 두 DNA 사이의 각 위치에서 서로 다른 문자의 개수)의 합이 가장 작은 새로운 DNA s를 구하고, 그 해밍 거리의 합을 출력하는 프로그램을 작성하는 문제입니다. 만약 그러한 DNA s가 여러 개 존재한다면, 사전순으로 가장 앞서는 것을 출력해야 합니다.

• 입력: 첫째 줄에 DNA의 수 N(1 ≤ N ≤ 1,000)과 DNA의 길이 M(1 ≤ M ≤ 50)이 주어집니다. 둘째 줄부터 N개의 줄에 DNA 문자열이 주어집니다.
• 출력: 첫째 줄에 해밍 거리의 합이 가장 작은 DNA 문자열을 출력하고, 둘째 줄에 그 해밍 거리의 합을 출력합니다.

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

풀이: 열(Column) 단위 탐색과 그리디(Greedy) 알고리즘

해밍 거리의 합을 최소화하려면, 각 자리(인덱스)마다 주어진 N개의 DNA들 중 가장 많이 등장한 문자를 선택하면 됩니다. 가장 많이 등장한 문자를 선택하는 것이 그 자리에서 발생하는 해밍 거리를 최소화하는 최적의(Greedy) 선택입니다.

• 열(Column) 단위 탐색: 문자열을 행(Row)으로 볼 때, 바깥쪽 반복문은 문자열의 길이(M)만큼 순회하고, 안쪽 반복문은 DNA의 개수(N)만큼 순회합니다. 즉, 0번째 인덱스의 문자들을 N개의 DNA에서 모두 확인한 뒤, 다음 인덱스로 넘어가는 수직적인 탐색을 수행합니다.
• 빈도수 계산 및 사전순 선택: * 'A', 'C', 'G', 'T'의 등장 횟수를 저장할 크기 4의 배열 cnt를 사용합니다.
  • 안쪽 반복문이 끝나면 cnt 배열을 순회하여 가장 많이 등장한 문자(max)를 찾습니다.
  • 이때, 비교 조건이 cnt[j] > max 이므로, 빈도수가 같은 문자가 여러 개 있더라도 먼저 등장한 문자가 선택됩니다. 사전에 dna 배열을 {'A', 'C', 'G', 'T'}로 사전순으로 배치해 두었기 때문에, 사전순으로 가장 앞서는 DNA를 출력하라는 문제의 까다로운 조건이 별도의 예외 처리 없이 자연스럽게 해결됩니다.
• 해밍 거리 합산: 선택된 문자를 StringBuilder에 추가하고, 그 자리에서 발생한 해밍 거리(전체 N개 중 가장 많이 등장한 문자의 개수를 뺀 나머지, 즉 n - max)를 전체 해밍 거리 합(ans)에 누적합니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int n = Integer.parseInt(st.nextToken());
       int m = Integer.parseInt(st.nextToken());

       String[] a = new String[n];
       for (int i = 0; i < n; i++) {
          a[i] = br.readLine();
       }

       // 사전순 선택을 위해 A, C, G, T 순서로 배열 배치
       char[] dna = {'A', 'C', 'G', 'T'};
       StringBuilder sb = new StringBuilder();
       int ans = 0;
       
       // 각 자리(인덱스)별로 탐색
       for (int i = 0; i < m; i++) {
          int[] cnt = new int[4];
          
          // N개의 DNA 문자열에서 i번째 글자 빈도수 집계
          for (int j = 0; j < n; j++) {
             char c = a[j].charAt(i);
             if (c == 'A')
                cnt[0]++;
             else if (c == 'C')
                cnt[1]++;
             else if (c == 'G')
                cnt[2]++;
             else
                cnt[3]++;
          }

          int max = 0;
          char c = 'A';
          // 가장 많이 등장한 문자 찾기 (동률일 경우 사전순으로 앞서는 것 선택)
          for (int j = 0; j < 4; j++) {
             if (cnt[j] > max) {
                c = dna[j];
                max = cnt[j];
             }
          }
          
          sb.append(c);
          // 해밍 거리 누적: 전체 개수 - 가장 많이 등장한 문자의 개수
          ans += n - max;
       }

       bw.write(sb.toString() + "\n" + ans);

       bw.flush();
    }
}

알고리즘 분류

그리디 알고리즘 (Greedy), 문자열 (String)