백준 문제풀이 - 1969 번

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

1. 요약 및 풀이방법

N개의 DNA 데이터 조합을 받아 Hamming Distance의 합이 가장 작은 DNA s와
그 때의 Hamming Distance의 합을 구하는 문제이다.

Hamming Distance의 합이 가장 작다. -> 가장 비슷하다.
라는 생각으로 풀이했다.

즉, N개의 DNA 조합에서
0번 index 에서 최대 빈도를 보이는 문자 찾기,
1번 index 에서 최대 빈도를 보이는 문자 찾기,
...

각 data의 index별 문자의 개수를 count한다. (map 사용)
같은 빈도를 갖는 문자끼리는 사전순으로 앞서는 문자를 선택한다.
Hamming Distance의 합은 answer 문자열과의 차이를 모두 누적한다.

2. Code

#include <iostream>
#include <vector>
#include <utility>
#include <map>

int g_trial, g_len;
std::vector<std::string> g_data;
std::pair<std::string, int> g_answer;

void input()
{
    std::string tmp;

    std::cin >> g_trial >> g_len;
    g_data.reserve(g_trial);
    for (int i = 0; i < g_trial; i++)
    {
        std::cin >> tmp;
        g_data.push_back(tmp);
    }
}

void update_answer(std::map<char, int>& count)
{
    int max = 0;
    std::map<char, int>::reverse_iterator rit = count.rbegin();
    char answer;

    for (; rit != count.rend(); rit++)	// map은 사전순으로 자동 정렬 되어있으므로, 뒤에서부터 check한다.
    {
        if((*rit).second >= max)	// 같은 경우 사전순으로 앞서는 문자가 선택된다.
        {
            max = (*rit).second;
            answer = (*rit).first;
        }
    }
    g_answer.first.push_back(answer);
    g_answer.second += g_trial - max;	// g_trial의 경우 중 최대빈도 문자가 max번 있음.
    					// 따라서, 그 차이를 누적한다.
}

void solution()
{
    std::map<char, int> count;

    for (int col = 0; col < g_len; col++)	// row, col 순회 순서에 주의.
    {
        count.clear();
        for (int row = 0; row < g_trial; row++)
        {
            char tmp = g_data[row][col];	
            count[tmp]++;		// 현재 문자를 key로 사용하여 map에 저장한다.
        }
        update_answer(count);
    }
}

void print()
{
    std::cout << g_answer.first << std::endl;
    std::cout << g_answer.second << std::endl;
}

int main()
{
    input();
    solution();
    print();
    return (0);
}

3. 학습 내용

문자에 따라 map에 저장하여 순회를 돌며 카운팅 하는 과정이 머리속에서는 쉬웠지만,
직접 구현하다보니 헷갈리는 부분이 많았음.
위의 문제의 count자료구조의 경우 꼭 map을 사용하지 않고 vector를 사용해도 되지만,
의미를 좀 더 담기위해 map을 사용함.

하지만 data가 늘어나는 경우,
순회를 도는 과정에서 vector보다 시간이 많이 걸릴수도 있다는 우려가 있음.

4. 결과