[알고리즘] BOJ 1969 - DNA

회사일이 바빴다. 근래들어 잠도 부쩍 많아져서 이것저것 못하는 것들이 많다. 그래서 어제 저녁에 이걸 못풀면 잠을 안잘것이다 했는데, 15분만에 해결해서 당황했다. 그래도 어찌됐든 저찌됐든 여튼저튼 해결한건 해결한거니 기록을 남겨두기 위하여 포스팅을 한다.

 

 

---

 

 

이건 무슨 문제인가

 

어머니는 항상 옳으셨다.

 

가만히 문제를 읽다보면, 과거의 어머니가 항상 하시던 말씀이 떠오른다. 책을 읽으라고 하면 항상 불평했는데, 지금은 그 모든게 나의 독해력 향상을 위한 큰 그림이란걸 세삼 서른이 다 되어 느끼게 된다. 

 

사실 문제가 무슨 말 하는지를 모른다. 정말 2번, 3번 읽어봐도 모르겠다. 진지하게. 그래서 일단 구해야 하는것을 추려봤다.

 

구해야할 것

1. Hamming Distance의 합이 가장 작은 DNA

2. Hamming Distance의 합

 

위 두가지를 구해야 하는데, 그럼 Hamming Distance가 뭔지 알아야 할 것이다. 아래가 Hamming Distance의 정의다.

 

Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클오티드 문자가 다른 것의 개수이다.

 

오..... 아직도 모르겠어. 신비롭다. 한국말과 영어를 살짝 섞어 놓았을 뿐인데, 내가 알아들은것은 '각 위치의', '문자가 다른 것의 개수' 이거 2가지다. 안되겠다. 첫 번째 예시를 보자

 

 

까만건 글씨고 허연것은 바탕

 

바로 위에서 내가 주황색으로 표시한것을 기반으로 예제를 추론해 나가보자.

 

 

색깔은 생각보다 적다.

내가 아는거라고는, '각 위치의', '문자가 다른 것의 개수' 이었다. 그러다 위 그림처럼 결과를 도출하게 되었다.

결과 도출 과정은 다음과 같다.

 

1. 각 위치의 문자가 다른것의 개수가 Hamming Distance라는 것이다.

2. 그렇다면 arr[0][1], arr[1][1], arr[2][1]과 같이 동일한 열에 대하여, 각 행들을 비교를 해보자

3. 빨간색 글씨를 보면 알 수 있지만, T가 4번나오고 A가 한번나오는데, 정답엔 해당 위치에 T가 나오게 했다.

4. 다른곳도 동일하게 진행했다.

5. 아! 그렇다면, 가장 많이 나온 알파벳을 출력해주어야 하는 것이다.

6. 그럼 나머지 출력인 7은 어떻게 구하는 것일까

7. 각 열에서 최대 다수로 많은 알파벳을 제외한 나머지 알파벳의 개수구나.

 

이러한 문제해결과정을 가정하고 나머지 예시를 보았다.

뭐라는겨 하....

위 문제해결과정을 나머지 예시에 도입했을 때 예제출력과 동일하게 나왔다. 고로 현재까지는 내가 한 추론이 맞았다는 소리다. (물론 반례가 있을 수 있지만)

 

이건 무엇으로 풀었는가

그래서 이 문제를 푸는건 당연히 완전탐색으로 했다. 왜냐하면 각 행과 열을 모두 봐야하기 때문에 완전탐색으로 풀어주었다. 나머지는 코드를 보고 이해하기를 바란다. 나도 명색에 공대생이라고 이렇게 내 생각들을 글로 적는것은 적잖히 어려운 일이 아니다.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>

using namespace std;
int n, m, _max=-1, cnt=0;
char map[1001][51];
string ans = "";
int alphaMap[28][1001] = { 0, }; // -65 해줘야함
int main() {

	int n, m;
	scanf_s("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf(" %c", &map[i][j]);
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			alphaMap[(int)map[j][i] - 65][i] ++;
		} // 다 돌았어 다 완성이 됐어
		// 그럼 이제 i 만큼 또 돌아가야겠지

		int idx = -1;
		_max = -1;
		for (int j = 0; j < 26; j++) {
			// max인 index찾아서
			if (alphaMap[j][i] > _max) {
				_max = alphaMap[j][i];
				idx = j;
			}
		}
		for (int j = 0; j < 26; j++) {
			if (j == idx) {
				continue;
			}
			else {
				cnt += alphaMap[j][i];
			}
		}
		ans += ((char)(idx + 65));
	}
	cout << ans << endl;
	cout << cnt << endl;
	return 0;
}

 

결과

4ms 시간만큼 찝찝한 시간도 없다.

 

---

솔직히 정말로 이건 정말로 순전히 운으로 맞은 기분이다. 저렇게 추론하는 것도 능력이라고는 하지만, 테스트 케이스가 3개나 되어서 쉽게 추론할 수 있었던 것이다. 좀 더 독해력을 키워야 할 필요를 느꼈다.