[Algorithm/Java] 백준 1969번 - DNA

---

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

---

🔍 문제 풀이

문제 도식화

• > 비교면 동률은 갱신하지 않아 처음(사전순 가장 앞선) 문자가 그대로 유지됨
• 열마다 최빈수 max만 알면 그 열의 해밍 거리(각 행과의 차이)가 곧 n - max라서, 굳이 모든 행과 sb를 직접 비교해 불일치를 세줄 필요가 없음

해밍 거리는 길이가 같은 두 문자열에서, 같은 위치에 있는 문자들이 서로 다른 개수를 의미

💻 코드

해밍 거리 바로 계산

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static char[][] arr;
    static int[] nums;

    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());

        arr = new char[n][m];

        for(int i=0; i<n; i++){
            String line = br.readLine();
            for(int j=0; j<m; j++){
                arr[i][j] = line.charAt(j);
            }
        }

        solve();
    }

    static void solve(){
        int dist = 0;

        StringBuilder sb = new StringBuilder();

        // 각 열의 최빈 문자로 sb 구성
        for(int j=0; j<m; j++){
            nums = new int[26];

            for(int i=0; i<n; i++){
                int digit = arr[i][j] - 'A';
                nums[digit] ++;
            }

            int max = -1;
            char ch = ' ';
            for(int i = 0; i<26; i++){
                if(nums[i] > max){ // 동률 무시 -> 사전순 유지
                    max = nums[i];
                    ch = (char)(i + 'A');
                }
            }
            sb.append(ch);
            // 열에서 가장 많이 나온 문자 개수: max
            // 즉, 그 열에서 같은 문자인 행은 max개, 다른 문자인 행은 n - max개
            dist += (n-max); // 해당 열의 해밍 거리 누적

        }

        System.out.println(sb);
        System.out.print(dist);

    }
}

모든 행과 sb를 직접 비교 (비효율)

모든 행을 순회하며 각 행과의 차이(해밍 거리)를 일일이 계산하여 더하기 때문에 비효율

static void solve() {
    StringBuilder sb = new StringBuilder();

    // 1) 각 열의 최빈 문자로 sb 구성
    for (int j = 0; j < m; j++) {
        nums = new int[26];
        for (int i = 0; i < n; i++) {
            nums[arr[i][j] - 'A']++;
        }
        int max = -1;
        char ch = 'A';
        for (int i = 0; i < 26; i++) {
            if (nums[i] > max) { // 동률 무시 -> 사전순 유지
                max = nums[i];
                ch = (char) (i + 'A');
            }
        }
        sb.append(ch);
    }

    // 2) 모든 행과 sb를 직접 비교하여 해밍 거리 계산
    int dist = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] != sb.charAt(j)) dist++;
        }
    }

    System.out.println(sb.toString());
    System.out.println(dist);
}