[백준 1969] DNA (C#, C++) - soo:bak

문제 링크

1969번 - DNA

설명

N개의 DNA 문자열이 주어지고 모두 길이가 M으로 같을 때, 이들과의 해밍 거리 합이 최소가 되는 길이 M인 문자열을 찾는 문제입니다.

해밍 거리는 같은 위치에서 다른 문자의 개수를 의미합니다.

최소 해밍 거리를 만드는 문자열이 여러 개라면 사전순으로 가장 앞서는 것을 출력합니다.

접근법

해밍 거리는 같은 위치의 문자들끼리만 비교하므로, 각 위치를 독립적으로 처리할 수 있습니다.

예를 들어 ACGT, AGGT, TCGT 세 DNA가 있을 때, 첫 번째 위치에서 A가 2개, T가 1개이므로 A를 선택하면 불일치가 1개(T와 다름)입니다.

만약 T를 선택하면 불일치가 2개(A 두 개와 다름)가 되므로, 가장 많이 등장하는 문자를 선택하는 것이 그 위치에서의 불일치를 최소화합니다.

각 위치마다 A, C, G, T 네 문자의 등장 횟수를 세고, 가장 많이 등장한 문자를 선택합니다.

동률인 경우 사전순으로 앞서는 것을 선택해야 하므로, A, C, G, T 순서로 검사하면서 최대 빈도를 갱신하면 자연스럽게 사전순 우선이 적용됩니다.

해밍 거리의 합은 각 위치마다 선택되지 않은 문자의 개수를 모두 더한 값입니다.

즉, 전체 DNA 개수에서 선택된 문자의 등장 횟수를 뺀 값을 각 위치별로 합산합니다.

N은 1,000 이하, M은 50 이하이므로 모든 위치와 DNA를 순회하며 처리할 수 있습니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var first = Console.ReadLine()!.Split();
      var n = int.Parse(first[0]);
      var m = int.Parse(first[1]);

      var dna = new string[n];

      for (var i = 0; i < n; i++) dna[i] = Console.ReadLine()!;

      var order = new char[] {'A', 'C', 'G', 'T'};
      var consensus = new char[m];
      var distanceSum = 0;

      for (var pos = 0; pos < m; pos++) {
        var cnt = new int[4];

        for (var i = 0; i < n; i++) {
          var ch = dna[i][pos];
          if (ch == 'A') cnt[0]++;
          else if (ch == 'C') cnt[1]++;
          else if (ch == 'G') cnt[2]++;
          else cnt[3]++;
        }

        var bestIdx = 0;

        for (var j = 1; j < 4; j++) {
          if (cnt[j] > cnt[bestIdx]) bestIdx = j;
        }

        consensus[pos] = order[bestIdx];
        distanceSum += n - cnt[bestIdx];
      }

      Console.WriteLine(new string(consensus));
      Console.WriteLine(distanceSum);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef vector<string> vs;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vs dna(n);

  for (int i = 0; i < n; i++) cin >> dna[i];

  const char order[4] = {'A', 'C', 'G', 'T'};
  string consensus;
  consensus.reserve(m);
  int distanceSum = 0;

  for (int pos = 0; pos < m; pos++) {
    int cnt[4] = {0,};

    for (int i = 0; i < n; i++) {
      char ch = dna[i][pos];
      if (ch == 'A') cnt[0]++;
      else if (ch == 'C') cnt[1]++;
      else if (ch == 'G') cnt[2]++;
      else cnt[3]++;
    }

    int best = 0;

    for (int j = 1; j < 4; j++)
      if (cnt[j] > cnt[best]) best = j;

    consensus.push_back(order[best]);
    distanceSum += n - cnt[best];
  }

  cout << consensus << "\n" << distanceSum << "\n";

  return 0;
}