백준#1969 - DNA

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

1969번: DNA

그리디 알고리즘으로 분류된 1969번 DNA문제 입니다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _1969
{
    class Program
    {
 
        static void Main(string[] args)
        {
            //길이와 갯수 입력.
            string[] countLength = Console.ReadLine().Split(' ');
            int DNALength = int.Parse(countLength[1]);
            int DNACount = int.Parse(countLength[0]);
 
            //모든 DNA입력.
            var DNAArray = new string[DNACount];
 
            for (int i = 0; i < DNACount; i++)
                DNAArray[i] = Console.ReadLine();
 
            Dictionary<string, int> charDict = new Dictionary<string, int>();
 
            //답을 구할 문자열, 디스턴스.
            string strAnswer = "";
            int intAnswer = 0;
 
            //모든 DNA의 첫번째 문자부터 마지막 문자까지.
            for(int charAt = 0; charAt < DNALength; charAt++)
            {
 
                //각 DNA string을 하나씩 가져옴.
                for(int line = 0; line < DNACount; line++)
                {
                    int charCount;
                    string targetChar = DNAArray[line].Substring(charAt, 1);
                    if (charDict.TryGetValue(targetChar, out charCount))
                        charDict[targetChar] = charCount + 1;
                    else
                        charDict.Add(targetChar, 1);
                }
 
                //딕셔너리 각 요소를 돌며 최소값 찾기.
                string maxString = "ZZ";
                int maxCount = int.MinValue;
 
                foreach(KeyValuePair<string, int> kvp in charDict)
                {
                    if (maxCount == kvp.Value)
                    {
                        if (kvp.Key.CompareTo(maxString) == -1)
                            maxString = kvp.Key;
                    }
                    else if (maxCount < kvp.Value)
                    {
                        maxCount = kvp.Value;
                        maxString = kvp.Key;
                    }
                    
                }
                strAnswer += maxString;
                intAnswer += maxCount;
                charDict.Clear();
            }
 
            Console.WriteLine("{0}\n{1}", strAnswer, DNALength * DNACount - intAnswer);
        }
    }
}
 

 

ex)5 8

12345678

TATGATAC

TAAGCTAC

AAAGATCC

TGAGATAC

TAAGATGT

이와 같이 예시가 있습니다. 스트링 하나하나를 따로 보는게 아니라 각 스트링의 0번을 모두 보고 1번을 모두 보고

하기 위해 위에 인덱스를 붙였습니다.

 

저는 각 인덱스 알파벳의 대세를 골라줬습니다. 1번줄에 문자가 T T A T T 이런 식으로 있으며 이를 갯수를 세주었습니다. 갯수를 세는데는 Dictionary를 사용했습니다. 그리고 가장 많이 선택된 T와 그 갯수 4개가 나오며 최종 출력할

문자열에 T를 이어줍니다. 또한 최종 갯수에 4를 더해줍니다.

다음 2번줄에 A가 4개 G가 한개 이므로 A를 문자열에 이어주고 A의 카운트를 최종 갯수에 더해줍니다.

 

그럼 TAAGATAC가 나오며 갯수가 33이 나오는데 이는 각 스트링의 대세 문자를 골랐을 때 그 갯수가 되며

대세가 아닌 문자들을 구하려면 모든 문자의 갯수 5 * 8에서 대세의 갯수를 빼주면 되겠습니다.