[백준] 1969 DNA

문제 :

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

1969번: DNA

 

풀이 :

감으로 열간 비교를 통해 가장 많이 나온 문자가 그 자리 인덱스라는 것을 알았지만 문자간의 거리의 차를 모두 더하는 것이 어떻게 하면 좋을지 방법이 생각나지 않았다.

 

그러다

https://gusdnr69.tistory.com/31

요 블로그를 참고해 문자와 달랐던 값을 열로 카운트 했다는 점이 신기했다. (아직도 배울게 너무 많다니 많이 반성 된다 ..)

우선 문자를 string 배열에 한번에 담고, 

행 우선 비교가 아닌 열 우선 비교 word[j][i]를 통해 가장 많이 등장한 문자를 unordered_map으로 문자, 빈도수 로 저장한다.

 

그리로 또 한번의 for문을 통해 max_count와 max_index를 업데이트 시켜준 뒤 비교한 열 개수(N)에서 max 빈번도를 빼주어 

구하고자 한 s와 문자열 s1, s2, ~ sN 중 다른 문자를 가진 문자의 개수를 구한다.

 

c++ 코드 :

//
//  1969_DNA.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/02/16.
//

#include <iostream>
#include <unordered_map>
using namespace std;
int N, cnt;

unordered_map<char, int> map;
int result_sum = 0;

int main(){
    cin >> N >> cnt;
    string s = "";
    string word[N];
    
    for(int i = 0; i < 26; i++){ //initial
        map['A' + i] = 0;
    }
    
    for(int i =0; i < N; i++){
        cin >> word[i];
    }
    
    for(int i =0; i < cnt; i++){ // 한 줄
        for(int j = 0; j < N; j++){
            map[word[j][i]]++;
        }
        
        int max_count = 0; int max_index = 0;
        
        for(int j = 0; j < 26; j++){
            if(map[j+'A'] > max_count) {
                max_count = map[j+'A'];
                max_index = j;
            }
        }

        result_sum += N - max_count;
        s += max_index + 'A';
        
        map.clear();

        
    }
    
    cout << s << '\n';
    cout << result_sum << '\n';
    return 0;
}