백준 1969번 ☆

문제

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

1969번: DNA

import java.util.Scanner;

public class Main1969 {
	
	static int N;
	static int M;
	static String[] dna;
	static boolean[] visit;
	static char[] dnas = {'A', 'T', 'G', 'C'};
	static char[] temp;
	static int min = Integer.MAX_VALUE;
	static String ans;
	
	public static void compare(int cnt) {
		int count=0;
		
		if (cnt == M) {
			for(int i=0; i<dna.length; i++) {
				for(int j=0; j<M; j++) {
					if (temp[j] != dna[i].charAt(j)) {
						count++;
					}
				}
			}
			
			if (count < min) {
				min = count;
				for (int i=0; i<M; i++) {
					ans += temp[i];
				}
			}

		} else {
			for(int i=0; i<M; i++) {
				if (!visit[i]) {
					if (i>3) {
						temp[cnt] = dnas[i];
						visit[i] = true;
						compare(cnt+1);
						visit[i] = false;
					} else {
						temp[cnt] = dnas[i];
						visit[i] = true;
						compare(cnt+1);
						visit[i] = false;
					}
					
				}
			}
		}
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		dna = new String[N];
		visit = new boolean[dnas.length];
		temp = new char[M];
		
		for (int i=0; i<dna.length; i++) {
			dna[i] = sc.next();
		}
		
		sc.close();
		
		compare(0);
		
		System.out.println(ans);
		System.out.println(min);
	}
}

import java.util.Scanner;

public class Main1969_1 {

	static int N;
	static int M;
	static String[] dna;
	static char[] temp;
	static int sum;
	
	public static void compare() {
		
		for (int i=0; i<M; i++) {
			int[] count = new int[4];
			
			for (int j=0; j<N; j++) {
				
				switch(dna[j].charAt(i)) {
				case 'A' :
					count[0]++;
					break;
				case 'C' :
					count[1]++;
					break;
				case 'G' :
					count[2]++;
					break;
				case 'T' :
					count[3]++;
					break;
					
				}
			}
			
			int max = 0;
			int index = 0;
			
			for (int k=0; k<count.length; k++) {
				if (count[k] > max) {
					max = count[k];
					index = k;
				}
			}
			
			switch (index) {
			
			case 0 :
				temp[i] = 'A';
				break;
			case 1 :
				temp[i] = 'C';
				break;
			case 2 :
				temp[i] = 'G';
				break;
			case 3 :
				temp[i] = 'T';
				break;
			}
			
			sum += N - max;
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		dna = new String[N];
		temp = new char[M];
		
		for (int i=0; i<dna.length; i++) {
			dna[i] = sc.next();
		}
		
		compare();
		
		String string = new String(temp);
		
		System.out.println(string);
		System.out.println(sum);
	}
}

1. 첫번째 코드는 오답, 두번째 코드가 정답이다.

 

2. 문제이해부터 풀이까지 죄다 실수 투성이었다.

 

3. 첫번째 코드의 접근 방식은 각 자리에 A,C,G,T 4가지의 DNA를 배열에 넣으려했는데 경우의 수를 계산해보니 최대 4의 50제곱까지 나오기에 완전탐색으로 풀기에는 무리가 있다 판단했다. 사실 그 부분뿐만 아니라 다른 여러부분에서도 막혔지만..

 

4. 결국 못참고 구글링을 해서 문제를 해결했다. 다만 풀이도중 4가지의 DNA를 사전순으로 switch문내에서 작성하지 않아 계속 틀리면서 헤맸다. 문제를 좀 더 꼼꼼히 읽어야만 한다.

 

5. 이런 방식 말고도 여러 방식을 이용해서 해결할 수 있다. 다만 완전히 내 힘으로 푼 문제가 아니니 추후에 꼭 다시 풀어보자.