문제

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

풀이

첫번째 풀이

1. 주어진 모든 문자열에 대해, 각 열에서 가장 많이 등장한 문자를 찾아서 target 문자열에 더한다.
2. 문자의 출현 빈도가 동일하면, 사전 순으로 더 앞에 오는 문자를 선택한다.
3. target 문자열 완성
4. n개의 문자열과 target 문자열을 비교해서 해밍 거리의 합을 구한다.

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

int N, M;
vector<string> v; 
map<char, int> m; 

void initMap() { 
	m['A'] = 0; 
	m['C'] = 0; 
	m['G'] = 0; 
	m['T'] = 0; 
}

char findMaxFreqChar() { 
	int maxFreq = -1; 
	char temp = 'A';
	
	for(auto e: m){
		int freq = e.second; 

		// 빈도수가 동일한 경우에는 
		// 사전 순으로 앞에 오는 문자가 먼저 temp에 저장된다. 
		if(freq > maxFreq){ 
			maxFreq = freq; 
			temp = e.first; 
		}
	}
	
	return temp; 
}

string findMinDiffStr(){
	string str = ""; 
	
	for(int i = 0; i < M; i++){
		for(int j = 0; j < N; j++){
			// 행 변화, 열 고정 
			char ch = v[j][i]; 
			
			// 각 문자의 등장 횟수 갱신 
			m[ch] += 1; 
		}

		// 각 열에 대해 빈도수가 가장 높은 문자를 string에 더한다.
		str += findMaxFreqChar();
		initMap(); 
	}

	return str; 
}

int calcHammingDistance(string target){
	int sum = 0; 
	for(int i = 0; i < N; i++){
		int cnt = 0; 
		for(int j = 0; j < M; j++){
			if(target[j] != v[i][j]) cnt++; 
		}
		sum += cnt; 
	}
	return sum; 
} 

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

	initMap(); 

	cin >> N >> M; 

	for(int i = 0; i < N; i++){
		string s; 
		cin >> s; 
		v.push_back(s); 
	}

	string target = findMinDiffStr();
	int answer = calcHammingDistance(target);

	cout << target << "\n" << answer; 
	
	return 0;
}

target 문자열과 해밍 거리를 모두 출력해야 하는데, 해밍 거리만 출력해서 오답을 받았었다. 입력, 출력을 제대로 했는지 꼭 확인하자!!!!

그리고 이 문제는 각 열마다 가장 많이 등장한 문자가 무엇인지 찾을 때 O(NM), n개의 문자열과 target 문자열을 비교해서 해밍 거리의 합을 구할 때 O(NM)이어서, 총 O(NM)의 시간복잡도가 걸린다고 볼 수 있다.

더 효율적인 풀이

각 열에 대해 가장 많이 등장한 문자가 무엇인지 구할 때, 해밍 거리도 구할 수 있는 방법이 있다. 바로 전체 행의 개수에서 가장 많이 등장한 문자의 빈도수를 빼면 된다.

즉, 첫번째 풀이는 target 문자열을 구한 다음에 각 행마다 문자열 하나씩 비교했는데 (가로 방향)

두번째 풀이는 각 열마다 가장 많이 등장한 문자도 찾고, 그 문자에 해당하지 않는 문자들의 개수를 통해 해밍 거리도 구한다. (세로 방향)

위의 그림에서, 형광펜으로 칠하지 않은 문자들의 개수를 세로 방향으로 센다고 보면 된다.

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

int N, M;
vector<string> v; 
map<char, int> m; 

void initMap() { 
	m['A'] = 0; 
	m['C'] = 0; 
	m['G'] = 0; 
	m['T'] = 0; 
}

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

	initMap(); 

	cin >> N >> M; 

	for(int i = 0; i < N; i++){
		string s; 
		cin >> s; 
		v.push_back(s); 
	}

	string str = ""; 
	int hammingDist = 0; 
	
	for(int i = 0; i < M; i++){
		for(int j = 0; j < N; j++){
			// 행 변화, 열 고정 
			char ch = v[j][i]; 
			
			// 각 문자의 등장 횟수 갱신 
			m[ch] += 1; 
		}

		// 각 열에 대해 빈도수가 가장 높은 문자를 구한다.
		// 전체 행의 개수에서 해당 빈도수를 빼면, 그 열에 대한 해밍 거리를 구할 수 있다. 
		int maxFreq = -1; 
		char temp = 'A';
		for(auto e: m){
			int freq = e.second; 
	
			// 빈도수가 동일한 경우에는 
			// 사전 순으로 앞에 오는 문자가 먼저 temp에 저장된다. 
			if(freq > maxFreq){ 
				maxFreq = freq; 
				temp = e.first; 
			}
		}

		str += temp;
		hammingDist += (N - maxFreq);
		
		initMap();
	}

	cout << str << "\n" << hammingDist; 
	
	return 0;
}