[C#]백준 1969 DNA - Hide

반응형

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

문제 요약

주어진 문자열들의 각 열에서 가장 많은 문자(대표)들을 모아서 만든 문자열과,

각 열에서 대장과 다른 문자의 개수를 합한 수(Hamming Distance) 출력하기

(대표 문자가 여러 개일 시 사전순 정렬로 대표 문자 선출)

 

 

 

참고

Hamming Distance를 최소화하기 위해서는 그 열에서 가장 많이 등장하는 문자를 대표로 만들어 대표와 다른 문자의 개수를 구하는 것이 좋다. 다수결과 비슷한 원리

쉽게 말해서 Hamming Distance 최솟값 => 그 열에서 '대표'와 다른 문자가 몇 개 있는가 찾으면 되는 것

대표가 아닌 문자

예를 들어 예제 1의 각 열의 대표는 각각 'T', 'A', 'A', 'G', 'A', 'T', 'A', 'C'이고, Hamming Distance는 7개다.

 

 

 

풀이

var t=Console.ReadLine().Split().Select(int.Parse).ToList();
var a=new string[t[0]];
for(int i=0;i<t[0];i++)a[i]=Console.ReadLine();
var r="";var s=0;
for(int i=0;i<t[1];i++)
{
    var c=a.Select(x=>x[i]).ToList();
    var f=c.GroupBy(x=>x).OrderBy(x=>-x.Count()).ThenBy(x=>x.Key).First();
    r+=f.Key;
    s+=t[0]-f.Count();
}
Console.Write($"{r}\n{s}");

---

요즘 연말이라 우울 맥스 찍는 듯; 제발 정신 좀 차려....