[백준] 1969 DNA

1. 문제

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

1969번: DNA

2. 접근방법

Hamming Distance가 가장 작은 새로운 DNA를 찾는 문제

처음에 기존 DNA들중 가장 작은 Distance를 찾는 줄 알았는데

Distance가 가장 작은 새로운 DNA하나를 만드는 문제였다.

 

조심하면서 풀자

 

문제 자체는 N과 M이 작아 완전탐색으로 풀이하면 쉽게 풀이 가능하다.

 

다른 DNA들과 Distance가 가장 작다 -> 같은 문자가 가장 많다.로 해석 하면 된다.

 

각 자릿수에서 가장 많은 문자를 정답 str에 넣으면 된다.가장 많은 문자가 여러개라면 사전순으로 넣으면 된다.

 

팁으로 갯수를 셀때 char형은 아스키코드로 자동 변환되기 때문에 배열의 index로 쓸 수 있다.

count['A']++ 이런식으로 코딩하면 더욱 쉽게 풀이 가능할 것이다.

3. 자바 코드

package backjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P1969DNA {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        String [] str = new String[N];
        for(int i = 0 ; i < N ; i++){
            str[i] = br.readLine();
        }
        String answer = "";
        int minSum = 0;
        for(int i = 0 ; i < M ; i++){
            int [] cnt = new int [100];
            for(int j = 0 ; j < N ; j++){
                cnt[str[j].charAt(i)]++;
            }
            int max = 0;
            char maxChar = 'a';
            for(char j = 'A' ; j <= 'Z' ; j++){
                if(cnt[j] > max){
                    max = cnt[j];
                    maxChar = j;
                }
            }
            minSum += (N-max);
            answer += maxChar;
        }
        System.out.println(answer);
        System.out.println(minSum);
    }
}

4. 마치며

얼마만의 문제풀이인지 재밌네