[1969번] DNA

문제 기출 : [https://www.acmicpc.net/problem/1969]

 

 

풀이 방법

[그리디알고리즘] 접근   해답의 가장 큰 핵심은 각 N개의 DNA의 각 M번째 자리수(char)가 가장 많은 문자를 출력하고 카운팅해주면 된다.   가장 좋았던 조건. 체크해야할 문자를 4개로 제한 한것. (만약 제한이 없고 Alphanumeric이었다면 과연 어땠을까..?ㅠㅠ)   2중 for문을 이용해서 N개의 DNA를 탐색하면서 각 자리의 char를 체크한다. A면 A를 카운팅, T면 T를 카운팅 ····.   카운팅 된 수 중, 가장 큰 값을 채택하고 그 값을 N에서 뺀 것을 누적하여 더해주면 Hamming Distance의 합이 될 수 있다!!! 채택된 해당 max값을 가진 char를 가지고 온다. 그 값이 바로 우리가 구할 s의 자리 값이다.   난 이 부분에서 '사전식 우선순위'를 잊고 있었다. 그래서 왜 때문인지 계속 실패했다... 문제를 3번 정도 다시 읽어서야 사전식 우선순위를 추가하지 않았다는 사실을 깨달았다.... 바로 fix하고 돌려보니 성공...핳핳ㅎ.....

 

 

문제 풀이

public class Main {

	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = 0;
		int M = 0;
		StringTokenizer tokens = null;
		int ACount = 0;
		int TCount = 0;
		int GCount = 0;
		int CCount = 0;
		int maxCount = 0;
		int sumHammingDistance = 0;

		try {
			tokens = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(tokens.nextToken());
			M = Integer.parseInt(tokens.nextToken());
			
			String[] DNAs = new String[N];
			for (int i = 0; i < N; i++) {
				DNAs[i] = br.readLine();
			}
			
			for (int i = 0; i < M; i++) {
				ACount = 0;
				TCount = 0;
				GCount = 0;
				CCount = 0;
				
				for (int j = 0; j < N; j++) {
					switch (DNAs[j].charAt(i)) {
					case 'A':
						ACount++;
						break;
					case 'T':
						TCount++;
						break;
					case 'G':
						GCount++;
						break;
					case 'C':
						CCount++;
						break;
					default:
						break;
					}
				}
				
				maxCount = Math.max(ACount > TCount ? ACount : TCount, GCount > CCount ? GCount : CCount);
				sumHammingDistance += (N - maxCount);

				if(maxCount == ACount) {
					System.out.print('A');
				} else if(maxCount == CCount) {
					System.out.print('C');
				} else if(maxCount == GCount) {
					System.out.print('G');
				} else {
					System.out.print('T');
				}
			}

			System.out.println();
			System.out.println(sumHammingDistance);
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}