[코드포스 Practice6] B. Mammoth's Genome Decoding

The process of mammoth's genome decoding in Berland comes to its end!

One of the few remaining tasks is to restore unrecognized nucleotides in a found chain s. Each nucleotide is coded with a capital letter of English alphabet: 'A', 'C', 'G' or 'T'. Unrecognized nucleotides are coded by a question mark '?'. Thus, s is a string consisting of letters 'A', 'C', 'G', 'T' and characters '?'.

It is known that the number of nucleotides of each of the four types in the decoded genome of mammoth in Berland should be equal.

Your task is to decode the genome and replace each unrecognized nucleotide with one of the four types so that the number of nucleotides of each of the four types becomes equal.

 

Input

The first line contains the integer n (4 ≤ n ≤ 255) — the length of the genome.

The second line contains the string s of length n — the coded genome. It consists of characters 'A', 'C', 'G', 'T' and '?'.

 

Output

If it is possible to decode the genome, print it. If there are multiple answer, print any of them. If it is not possible, print three equals signs in a row: "===" (without quotes).

---

악.. 문제 보자마자 이해도 했고 어떻게 풀지 감도 잡혔는데 구현을 못해서 못 풀었다. 

 

내가 하려고 했던 건

 

1. 유전자 복원 못 하는 경우 제외시키기

        - 길이는 항상 4의 배수가 되어야 하므로 4의 배수가 아닌 경우 === 출력

        - 각 알파벳의 개수는 n/4개보다 작아야 하므로 n/4를 초과하는 경우 ===출력

 

2. ? 부분에 부족한 알파벳 출력

        - 입력된 문자열에서 A, C, G, T 개수를 센다

        - 부족한 알파벳 개수를 알고 싶으니 n/4에서 개수를 뺀다

        - ? 부분에 부족한 알파벳을 채워넣는다

 

여기서 ? 부분에 부족한 알파벳을 채워넣는다 <- 이걸 못했다. 헉?? 저기서 어떻게 꺼내오지?? 어떻게?? (20분이 흘러버림) 아무튼 지금은 시간도 있고 옆에 따신 차도 있으니 다시 생각해봐야겠다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
 
using namespace std;
using i64 = long long;
 
 
int main() {
    int n;
    string s;
    vector<int> v(4, 0);
    
    scanf("%d", &n);
    cin >> s;
    
    if(n % 4 != 0){
        printf("===");
        return 0;
    }
    
    
    for(int i = 0; i < s.length(); i++){
        if(s[i] == 'A')
            v[0]++;
        else if(s[i] == 'C')
            v[1]++;
        else if(s[i] == 'G')
            v[2]++;
        else if(s[i] == 'T')
            v[3]++;
    }
    
    
    
    for(int i = 0; i < 4; i++){
        if(v[i] > n/4){
            printf("===");
            return 0;
        }
    }
    
    for(int i = 0; i < 4; i++){
        v[i] = n/4 - v[i];
    }
    for(int i = 0; i < 4; i++){
        cout << v[i] << " ";
    }
    cout << endl;
    
    int index = 0;
    for(int i = 0; i < s.length(); i++){
        if(s[i] == '?'){
            
            while(v[index] < 0){
                index++;
            }
            
            if(index == 0)
                printf("A");
            else if(index == 1)
                printf("C");
            else if(index == 2)
                printf("G");
            else if(index == 3)
                printf("T");
            v[index]--;
            
        }
        else{
            cout << s[i];
        }
    }
    
    return 0;
}

일단 코드 백업

 

---

코드 짜면서 생각한 건 굳이 저 배열을 써서 해야 하나 싶었다. 뭔가 stack을 쓰면 편하겠다 생각했고 stl에 있을 것 같았음. 그리고.. 있었다! 그래서 stack에 부족한 알파벳을 넣어두고 출력할 때 하나씩 뽑았썼다. 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <functional>
 
using namespace std;
using i64 = long long;
 
 
int main() {
    int n;
    string s;
    vector<int> v(4, 0);
    
    scanf("%d", &n);
    cin >> s;
    
    if(n % 4 != 0){
        printf("===");
        return 0;
    }
    
    for(int i = 0; i < s.length(); i++){
        if(s[i] == 'A')
            v[0]++;
        else if(s[i] == 'C')
            v[1]++;
        else if(s[i] == 'G')
            v[2]++;
        else if(s[i] == 'T')
            v[3]++;
    }
    
    
    for(int i = 0; i < 4; i++){
        if(v[i] > n/4){
            printf("===");
            return 0;
        }
    }
    
    stack <char> st;
    for(int i = 0; i < 4; i++){
        v[i] = n/4 - v[i];
        for(int j = 0; j < v[i]; j++){
            if(i == 0)
                st.push('A');
            else if(i == 1)
                st.push('C');
            else if(i == 2)
                st.push('G');
            else if(i == 3)
                st.push('T');
        }
    }
   
    
    for(int i = 0; i < s.length(); i++){
        if(s[i] == '?'){
            cout << st.top();
            st.pop();
        }
        else{
            cout << s[i];
        }
    }
    
    return 0;
}

 

예헤이