[C++] 백준 DNA 해독

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

1672번: DNA 해독

풀이

염기서열의 길이 범위가 N(1 ≤ N ≤ 1,000,000) 이므로 한번의 반복문으로 해결해야 하는 문제입니다.

주어진 염기 표를 map 자료구조를 사용해 해싱하여 문제를 해결할 수 있습니다.

 

map<pair<char, char>, char> 을 선언하고 모든 표를 기록해줍니다.

문자열을 빼는 경우 string의 pop_back() 함수를 사용하면 됩니다.

#include <iostream>
#include <map>

using namespace std;

int main()
{
    // freopen("input.txt", "r", stdin);
    int n;
    string s;
    map<pair<char, char>, char> m;
    m[make_pair('A', 'A')] = 'A';  
    m[make_pair('A', 'G')] = 'C'; 
    m[make_pair('A', 'C')] = 'A'; 
    m[make_pair('A', 'T')] = 'G'; 
    m[make_pair('G', 'A')] = 'C'; 
    m[make_pair('G', 'G')] = 'G'; 
    m[make_pair('G', 'C')] = 'T'; 
    m[make_pair('G', 'T')] = 'A'; 
    m[make_pair('C', 'A')] = 'A'; 
    m[make_pair('C', 'G')] = 'T'; 
    m[make_pair('C', 'C')] = 'C'; 
    m[make_pair('C', 'T')] = 'G'; 
    m[make_pair('T', 'A')] = 'G'; 
    m[make_pair('T', 'G')] = 'A'; 
    m[make_pair('T', 'C')] = 'G'; 
    m[make_pair('T', 'T')] = 'T'; 

    cin >> n;
    cin >> s;

    while (true) {
        if (s.size() == 1)
            break;
        
        int k = s.size();
        char ss = m[make_pair(s[k-2], s[k-1])];
        s.pop_back();
        s.pop_back();
        s += ss;
    }
    cout << s << endl;
    return 0;
}