알고리즘/백준

[백준/c++] 1969번: DNA

녕이 2022. 7. 14. 12:44
728x90

 

 

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

 

1969번: DNA

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오

www.acmicpc.net

 

전체 문자열을 돌리면서 각 물질을 vector <pair <char, int>>에 넣으면서 카운팅하고 가장 큰 값을 가지는 물질을 minString에 추가해줬다. 그리고 vector안에 있는 가장 큰 물질 빼고 나머지 물질의 개수를 카운팅 하면 hd 가 나온다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool comp(pair<char, int> p1, pair<char, int> p2){
    if (p1.second == p2.second) return p1.first < p2.first;
    return p1.second > p2.second;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, hd = 0;
    string s[1001], minString = "";
    vector<pair<char, int>> v;
    cin >> n >> m;
    for(int i=0; i<n; i++) cin >> s[i];
    
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            bool flag = false;
            for(int k=0; k<v.size(); k++){
                if(s[j][i] == v[k].first){
                    v[k].second++; flag = true;
                }
            }
            if(!flag) v.push_back({s[j][i], 1});
        }
        sort(v.begin(), v.end(), comp);
        minString += v[0].first;
        for(int i=1; i<v.size(); i++)
            hd += v[i].second;
        v.clear();
    }
    
    cout << minString << '\n' << hd << '\n';
    return 0;
}

 

 

 

728x90