[백준/JAVA] 1969번: DNA

📖 문제

1969번: DNA

 

 

 

💡  풀이 방식

• 그리디

. k번째 문자를 선택할 때 k번째 문자들 중 가장 자주 나온 문자를 새로운 문자열의 k번째로 지정하며 문자열을 완성한다.

 

 

💥 유의사항

Hamming Distance의 합 구하는 식 : (N - k번째 문자열의 최대 등장 횟수) 한 값을 누적해 저장한다.

 

 

🔺 코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static String[] str;
    static int hd;  // Hamming Distance
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        str = new String[N];
        for (int i = 0; i < N; i++) {
            str[i] = br.readLine();
        }
        
        StringBuilder sb = new StringBuilder();
        
        for(int i = 0 ; i < M ; i++) {
            int[] cnt = new int[4]; // A C G T
            
            for(int j = 0 ; j < N ; j++) {
                char ch = str[j].charAt(i);
                
                switch(ch) {
                    case 'A':
                        cnt[0]++;
                        break;
                    case 'C':
                        cnt[1]++;
                        break;
                    case 'G':
                        cnt[2]++;
                        break;
                    case 'T':
                        cnt[3]++;
                        break;
                }
            }
            
            int idx = 0;    // 숫자 지정할 문자열의 인덱스
            int max = 0;    // 등장 횟수
            for(int k = 0 ; k < 4 ; k++) {
                if(cnt[k] > max || (cnt[k] == max && k < idx)) {
                    max = cnt[k]; // 가장 많이 사용된 알파벳 찾고
                    idx = k; // 그 인덱스 저장
                }
            }
            
            switch(idx) {
                case 0:
                    sb.append('A');
                    break;
                case 1:
                    sb.append('C');
                    break;
                case 2:
                    sb.append('G');
                    break;
                case 3:
                    sb.append('T');
                    break;
            }
            
            hd += N - max;  // Hamming Distance 합 갱신
        }
 
        System.out.println(sb.toString());
        System.out.println(hd);
    }
}
 

 

 

➕ 다른 풀이 방식

이렇게 짧게도 가능하다 한다.

[백준] 1969 DNA

 

 

마지막에 구한 Hamming Distance가 최소인 새 문자열과 DNA 배열을 비교해 문자가 다른 경우 cnt++를 했다.

(이게 더 이해하기 좋은 듯! 다음에 복습은 이 코드처럼 하도록 하겠다..)

[자바 / Java] 백준 1969 : DNA

---

💦 어려웠던 점

- 문제를 완전히 잘못 파악해서 1시간 정도 헤맸다. 각 줄의 문자열을 나머지 4개와 비교하며 다른 문자열의 갯수를 Hamming Distance로 저장하는 것인 줄 알았다.ㅠ

 

그게 아니고 DNA의 k번째 문자들 중 가장 자주 등장한 문자를 새 문자열의 k번째 문자로 설정하는 것이었다...😱

 

문제를 잘 읽자...

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준 1969번] DNA (java)