[백준] 1969번 / Java / DNA - 그리디

문제 - (https://www.acmicpc.net/problem/1969)

개인적으로 그리디 문제에 약하다고 생각해서 최근 그리디 문제를 많이 풀어보고 있다

여전히 오답이 많고 시간도 오래걸려서 좌절해있다가... 이 문제만큼은 자신있게 풀고 완벽히 이해하여 포스팅하려고 한다

(내가 생각해낸 방법이 기특해서 다음에 잊지않게 하기 위해서 ㅋㅋ)

 

그냥,, 간단하다!

주어진 DNA의 각 자릿수 알파벳의 수를 센다.각 자리마다 가장 많이 출현한 알파벳을 선정하면 그것이 답이된다!

 

우선, 알파벳의 길이만큼의 배열을 만들었다. 알파벳은 총 26개 있으니 alphabet[26]인 배열을 만든 것이다.

DNA들의 알파벳 수를 각 자릿수별로 세야하므로 alphabet[m][26]의 2차원 배열을 만들면 이렇게 해석할 수 있다.

DNA들의 m번째 자리에 있는 알파벳들의 수를 저장한다.

 

이 방법을 이용해서 모든 DNA를 순회하면서 각 자릿수별로 발견되는 알파벳의 카운트를 늘려주면 된다.

아래 코드를 보면 이해가 더 쉬울듯!

---

📌주의할 점

• char형을 int형으로 바꾸는 쉬운 방법은 'A'-0 이다. 즉, char에 int형 연산을 해주면 된다!! 이걸 활용해서 풀면 된다.

 

---

코드

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

/**
 * 30분 - 실버5
 */
public class DNA {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // dna 수
        int m = Integer.parseInt(st.nextToken()); // 문자열의 길이
        int[][] alphabet = new int[m][26];
        StringBuilder sb = new StringBuilder();
        int hammingDistance = 0;

        String[] dnas = new String[n];
        for (int i = 0; i < n; i++) {
            dnas[i] = br.readLine();

            for (int j = 0; j < m; j++) {
                /* 굳이 A가 int로 65인 것을 생각할 필요없이 'A'를 빼주면 된다. */
                alphabet[j][dnas[i].charAt(j) - 'A'] += 1;
            }
        }

        for (int i = 0; i < m; i++) {
            int max = alphabet[i][0];
            char target = 'A';
            for (int j = 0; j < 26; j++) {
                if (alphabet[i][j] > max) {
                    max = alphabet[i][j];
                    target = (char) (j + 'A');
                }
            }
            sb.append(target);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dnas[i].charAt(j) != sb.charAt(j)) hammingDistance++;
            }
        }

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