백준 1969번 - DNA

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

문제 분류는 그리디로 되어있는데

문자가 A,T,G,C로 제한되어 있지 않은 경우를 생각해서 브루트 포스로 문제를 해결해 보았다.

이를 위해 자료구조인 map을 이용했다.

map은 set처럼 중복된 key 값을 허용하지 않으면서 동시에 value값을 포함하고 있다.

문자가 기존 map에 포함되어 있는지 확인한 후, 존재 한다면 value값을 증가시켜 주었다.

다음으로 vector를 이용하여 value값이 큰 순으로(같다면 문자가 작은 순으로) 정렬을 해준 뒤에

전체 N개에서 가장 큰 value값을 빼주어Hamming Distance를 구해주었다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
 
struct str{
    char key;
    int value;
    
    str(char key,int value):key(key),value(value){};
};
 
bool operator<(str s1, str s2){
    if(s1.value==s2.value)
        return s1.key<s2.key;
    else
        return s1.value>s2.value;
}
 
int main(){
    
    int N,M;
    cin>>N>>M;
    
    string DNA[N];
    vector<vector<int>> distance(N,vector<int>(N,0));
    
    for(int i=0;i<N;i++){
        cin>>DNA[i];
    }
    
    int ans=0;
    map<char,int> mp;
    vector<str> vec;
    for(int j=0;j<M;j++){
        
        //중복 제거(map)
        for(int i=0;i<N;i++){
            if(mp.find(DNA[i][j])==mp.end())
                mp.insert(make_pair(DNA[i][j],1));
            else
                mp[DNA[i][j]]++;
        }
        
        map<char,int>::iterator itr;
        for(itr=mp.begin();itr!=mp.end();itr++){
            char key= itr->first;
            int value= itr->second;
            vec.push_back(str(key,value));
        }
        
        //value값 큰 순으로, value값 같으면 key값 작은 순으로
        sort(vec.begin(),vec.end());
        
        //전체에서 가장 많이 나온 key의 개수(value값) 빼주면 Hamming Distance 나온다
        ans+=N-vec[0].value;
        cout<<vec[0].key;
        
        mp.clear();
        vec.clear();
    }
    
    cout<<endl<<ans<<endl;
    return 0;
}